Comment puis-je trouver le chemin le plus court qui couvre tous les nœuds dans un dirigé cyclique graphique?

J'ai besoin d'un exemple du chemin le plus court d'un dirigés cyclique graphique à partir d'un nœud
(il devrait atteindre à tous les nœuds du graphe à partir d'un nœud à l'entrée).

S'il vous plaît si il y a un exemple, j'en ai besoin en C++, ou l'algorithme.

OriginalL'auteur Thaier Alkhateeb | 2009-04-25

  1. 5

    EDIT: Oups, mal lu la question. Merci @jfclavette pour la cueillette. Vieux la réponse est à la fin.

    Le problème que vous essayez de résoudre est appelé le Problème du voyageur de commerce. Il y a beaucoup de les solutions possibles, mais il est NP-complet, donc vous ne serez pas en mesure de résoudre de grands graphes.

    Vieille réponse:

    Ce que vous essayez de trouver est appelé le la circonférence d'un graphe. Il peut être résolu par le réglage de la distance d'un nœud à lui-même à l'infini et à l'aide de la De Floyd-Warshall algorithme. La longueur du cycle le plus court à partir du nœud i est alors simplement l'entrée dans la position ii.

    Il veut trouver le chemin le plus court que les visites de tous les nœuds, pas de cycle le plus court menant à l'original. Au moins, c'est ce que j'ai compris de la question.
    Merci, édité ma réponse.
    Il pourrait ne pas être tout à fait le Problème du voyageur de commerce puisqu'il semble y avoir aucune restriction à la question que les nœuds être visité exactement une fois. Donc, ce problème ne nécessite pas le graphe possède un cycle Hamiltonien.
    Aussi, le Problème du voyageur de commerce exige que tous les sommets être connecté. Dans la question ci-dessus, il ne dit pas que le graphique a tous les sommets connectés.

    OriginalL'auteur marcog

  2. 2

    En Pseudo-Code:

    //INPUT: graph G = (V,E)
//OUTPUT: shortest cycle length
min_cycle(G)
  min = ∞
  for u in V
    len = dij_cyc(G,u)
    if min > len
      min = len
  return min    

//INPUT: graph G and vertex s
//OUTPUT: minimum distance back to s
dij_cyc(G,s)
  for u in V
    dist(u) = ∞
                   //makequeue returns a priority queue of all V
  H = makequeue(V) //using dist-values as keys with s First In
  while !H.empty?
    u = deletemin(H)
    for all edges (u,v) in E
      if dist(v) > dist(u) + l(u,v) then
        dist(v) = dist(u) + l(u,v)
        decreasekey(H,v)

  return dist(s)

    Cela va un peu différente de Dijkstra sur chaque sommet. La mutation du Dijkstras
    a quelques différences clés. Tout d'abord, les distances sont mis à ∞, même les
    début de vertex. Deuxièmement, le début de sommet doit être mis sur la file d'attente à faire
    sûr que cela vient en premier, car ils ont tous la même priorité. Enfin, l'
    muté Dijkstras renvoie la distance de retour vers le nœud de départ. Si il n'y avait pas
    chemin de retour vers le début de vertex la distance reste ∞. Le minimum de tous ces
    de retour de l'muté Dijkstras est le chemin le plus court. Depuis Dijkstras pistes
    au pire en O(|V|^2) et min_cycle exécute cette forme de Dijkstras |V| temps, l'
    finale de courir de temps pour trouver le cycle le plus court est O(|V|^3). Si min_cyc retourne
    ∞ alors le graphe est acyclique.

    Pour retourner le chemin le plus court cycle seulement de légères modifications doivent être apportées.

    OriginalL'auteur agentargo

  3. 2

    Dans le cas non pondérés: Largeur de recherche.
    Dans le cas pondéré: Dijkstra est.

    OriginalL'auteur

  4. 1

    Pour les non pondérée graphique, BFS va faire le travail. Depuis, il existe un potentiel de cycle dans votre graphique, vous avez besoin de garder une trace de visité nœud (vous sorte de besoin de faire cela pour BFS de toute façon).

    Pour pondérée graphique, bellman–Ford algorithme peut être utilisé. Il est également capable de détecter les cycles.

    OriginalL'auteur leiz