Wie finde ich den kürzesten Weg, der alle Knoten in einem gerichteten zyklischen Graphen bedeckt?

Question

ich brauche die ein Beispiel für den kürzesten Weg eines gerichteten zyklischen Graphen von einem Knoten (Es für alle Knoten des Graphen von einem Knoten erreichen sollte, dass der Eingang sein wird).

Bitte, wenn es ein Beispiel ist, muss ich es in C ++, oder der Algorithmus.

Answer 1

EDIT: Oops, die Frage falsch verstanden. Dank @jfclavette dies für die Abholung. Alte Antwort ist am Ende.

Das Problem, das Sie lösen möchten, ist das rel="noreferrer"> Reisen. Es gibt viele mögliche Lösungen , aber es ist NP-vollständig, so dass Sie nicht in der Lage sein werden, lösen für große Graphen.

Alte Antwort:

Was Sie versuchen zu finden ist die Umfang eines Graphen genannt. Es kann durch Einstellen der Abstände von einem Knoten zu sich ins Unendliche und mit dem Floyd-Warshall Algorithmus. Die Länge des kürzesten Zyklus vom Knoten i ist dann nur der Eintrag in der Position II.

Answer 2

In Pseudocode:

//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)

Dies läuft eine etwas andere Dijkstra auf jeden Vertex. Das mutierte Dijkstras hat ein paar wichtige Unterschiede. Zunächst werden alle anfänglichen Abstände auf ∞, auch die Start Scheitel. Zweitens muss der Anfangspunkt in der Warteschlange zuerst gelegt werden, um zu machen sicher, kommt es zuerst, da sie alle haben die gleiche Priorität ab. Endlich, das mutiertes Dijkstras gibt den Abstand zurück zu dem Startknoten. Wenn es keine Pfad zurück zum Anfangsscheitelpunkt der Entfernung bleibt ∞. Das Minimum von all diesen Erträge aus dem mutierten Dijkstras ist der kürzeste Weg. Da Dijkstras läuft im schlimmsten Fall in O (| V | ^ 2) und min_cycle führt diese Form der Dijkstras | V | Zeiten, die Finale Laufzeit den kürzesten Zyklus zu finden, ist O (| V | ^ 3). Wenn MIN_CYC zurückkehrt ∞ dann der Graph azyklisch ist.

Um den tatsächlichen Pfad des kürzesten Zyklus zurückkehrt nur geringfügige Änderungen vorgenommen werden müssen.

Answer 3

Im ungewichteten Fall: Breitensuche . Im gewichteten Fall. Dijkstra

Answer 4

Für nicht gewichtete Graph wird BFS den Job. Da es Potenzial Zyklus in Ihrem Diagramm ist, müssen Sie den Überblick über besuchten Knoten halten (Sie Art dies ohnehin für BFS tun müssen).

Für gewichteten Graphen, Bellman-Ford-Algorithmus verwendet werden. Es ist auch in der Lage Zyklus zu erkennen.