Grafik - Wie finde ich den minimalen gerichteten Zyklus (minimales Gesamtgewicht)?

Question

Hier ist ein Verbrauch:

wären G a gewichtete gerichtete Graphen mit n Ecken und Kanten m sein, wobei alle Kanten positives Gewicht haben. Ein gerichteter Zyklus ist ein gerichteter Pfad, der am selben Eckpunkt beginnt und endet und mindestens eine Kante enthält. Geben Sie einen O (n^3) -Algorithmus an, um einen gerichteten Zyklus in G mit minimalem Gesamtgewicht zu finden. Ein Teilguthaben wird für einen O ((n^2) * m) -Algorithmus vergeben.

---

Hier ist mein Algorithmus.

Ich mache eine DFS. Jedes Mal, wenn ich eine back edge finde, weiß ich, dass ich einen gerichteten Zyklus habe.

Dann werde ich vorübergehend rückwärts gehen entlang der parent array (bis ich durch alle Ecken in den Zyklus reisen) und berechnen Sie die total weights.

Dann vergleiche ich die total weight dieses Zyklus mit min. min nimmt immer die minimalen Gesamtgewichte. Nachdem das DFS beendet ist, wird auch unser minimaler gesteuerter Zyklus gefunden.

---

Ok, dann über die Zeit Komplexität.

Um ehrlich zu sein, ich kenne die Zeit Komplexität meines Algorithmus nicht.

Für DFS verwendet die Traversierung O (m + n) (wenn m die Anzahl der Kanten und n die Anzahl der Ecken ist). Für jeden Knoten kann er auf einen seiner Vorfahren verweisen und somit einen Zyklus bilden. Wenn ein Zyklus gefunden wird, wird O (n) benötigt, um die Gesamtgewichte zusammenzufassen.

Also ich denke, die Gesamtzeit ist O (m + n * n). Aber offensichtlich ist es falsch, wie in der Verbrauchssteuer angegeben, ist die optimale Zeit O (n^3) und die normale Zeit ist O (m * n^2).

---

Kann mir jemand helfen mit:

1. Ist mein Algorithmus korrekt?
2. Was ist die zeitliche Komplexität, wenn mein Algorithmus korrekt ist?
3. Gibt es einen besseren Algorithmus für dieses Problem?

Answer 1

Sie Floyd-Warshall Algorithmus hier verwenden können.

Der Floyd-Warshall Algorithmus findet kürzesten Weg zwischen alle Paare von Vertices

Der Algorithmus ist dann sehr einfach, gehe über alle Paare , und finde das Paar, das dist(u,v)+dist(v,u) minimiert, da dieses Paar auf einem Zyklus von u bis u mit Gewicht dist(u,v)+dist(v,u) anzeigt. Wenn das Diagramm auch Eigenschleifen erlaubt (eine Kante (u,u)), müssen Sie diese auch alleine überprüfen, da diese Zyklen (und nur sie) nicht vom Algorithmus überprüft wurden.

Pseudocode:

run Floyd Warshall on the graph 
min <- infinity 
vertex <- None 
for each pair of vertices u,v 
    if (dist(u,v) + dist(v,u) < min): 
      min <- dist(u,v) + dist(v,u) 
      pair <- (u,v) 
return path(u,v) + path(v,u) 

path(u,v) + path(v,u) ist tatsächlich der Weg von u zu v gefunden und dann von v zu u, welches ein Zyklus.

Die Laufzeit des Algorithmus ist O(n^3), seit floyd-warshall ist der Flaschenhals, da die Schleife O(n^2) Zeit dauert.

Ich denke, Korrektheit hier ist trivial, aber lassen Sie mich wissen, wenn Sie mit mir nicht einverstanden sind und ich werde versuchen, es besser zu erklären.

Answer 2

„Für jeden Scheitelpunkt, könnte es zu einer ihrer Vorfahren zurückweisen und bildet somit einen Zyklus“

ich denke, es könnte wieder zu einem seiner Vorgänger zeigen, was bedeutet, N

Auch Wie wirst du Eckpunkte markieren, wenn du aus seinem dfs kommst, du kannst von einem anderen Eckpunkt dorthin zurückkehren und es wird ein anderer Zyklus sein. Das ist also nicht mehr (n + m) dfs.

1. So ur algo ist unvollständig
2. hier gilt das gleiche

3. Während eines dfs, ich denke, der Vertex sollte entweder ungesehen sein, oder überprüfen, und für überprüft Sie können das Mindestgewicht für den Pfad zum Startpunkt speichern. Wenn Sie also auf einer anderen Stufe eine Kante zu diesem Knoten finden, müssen Sie nicht mehr nach diesem Pfad suchen. Dieses dfs findet den minimalen gerichteten Zyklus, der den ersten Scheitelpunkt enthält. und es ist O (n^2) (O (n + m) wenn du den Graph als Liste speicherst)

Also, wenn es von irgendeinem anderen Scheitelpunkt aus geht, wird es O (n^3) sein (O (n *) (n + m))

Sorry, für mein Englisch, und ich bin nicht gut in Terminologie

Answer 3

Ist mein Algorithmus korrekt?

Nein. Lassen Sie mich ein Gegenbeispiel geben. Stellen Sie sich vor Sie DFS ab u, gibt es zwei Wege p1 und p2u-v und 1 Pfad p3 von v zurück zu u, p1 kürzer als p2.

Angenommen, Sie, indem der p2 Weg zu v, und gehen Sie zurück zu u durch Pfad p3 zu starten. Ein Zyklus gefunden, aber anscheinend ist es nicht das Minimum. Dann fahren Sie fort, u zu erforschen, indem Sie den Pfad p1 nehmen, aber seit v vollständig erforscht ist, endet das DFS, ohne den minimalen Zyklus zu finden.