Habe ich Recht mit den Unterschieden zwischen Floyd-Warshall-, Dijkstra- und Bellman-Ford-Algorithmen?

Ich habe die drei studiert und gebe meine Schlussfolgerungen von ihnen weiter unten an. Könnte mir jemand sagen, ob ich sie genau genug verstanden habe oder nicht? Vielen Dank.

1. Dijkstra - Algorithmus wird nur dann verwendet , wenn Sie eine Hand haben , und Sie wollen den kleinsten Pfad von einem Knoten zum anderen kennen, aber nicht in Fällen wie diesem .

2. Der Floyd-Warshall-Algorithmus wird verwendet, wenn einer der Knoten eine Quelle sein kann. Sie möchten also, dass die kürzeste Entfernung von einem Quellknoten zu einem beliebigen Zielknoten besteht. Dies schlägt nur bei negativen Zyklen fehl.

3. Bellman-Ford wird wie Dijkstra verwendet, wenn es nur eine Quelle gibt. Dies kann mit negativen Gewichten umgehen und funktioniert genauso wie Floyd-Warshall, abgesehen von einer Quelle, oder? (Dies ist der, bei dem ich mich am wenigsten sicher bin.)

Der Dijkstra-Algorithmus wird nur verwendet, wenn Sie über eine einzige Quelle verfügen und den kleinsten Pfad von einem Knoten zum anderen ermitteln möchten. Er schlägt jedoch fehl [in Diagrammen mit negativen Kanten].

Der Dijkstra-Algorithmus ist ein Beispiel für einen Single-Source-Shortest- Path- oder SSSP- Algorithmus. Jeder SSSP Algorithmus berechnet die kürzeste Pfad Abständen von einem ausgewählten Quellknoten an jedem anderen Knoten in dem Graph. Darüber hinaus wird eine kompakte Darstellung aller kürzesten Pfade von zu jedem anderen Knoten in Form eines Stammbaums berechnet . Ist im Wikipedia-Code das übergeordnete Element von in diesem Baum.$s$$s$previous[v]$v$

Das Verhalten des Dijkstra-Algorithmus in Diagrammen mit negativen Flanken hängt von der konkreten Variante ab, die zur Diskussion steht. Einige Varianten des Algorithmus, wie der in Wikipedia, werden immer schnell ausgeführt, aber bei negativen Flanken werden die kürzesten Pfade nicht korrekt berechnet. Andere Varianten, wie die in diesem Skript, berechnen die kürzesten Pfade immer korrekt (es sei denn, es ist ein negativer Zyklus von der Quelle aus erreichbar), benötigen jedoch im schlimmsten Fall exponentielle Zeit, wenn negative Flanken vorliegen.

Der Floyd-Warshall-Algorithmus wird verwendet, wenn einer der Knoten eine Quelle sein kann. Sie möchten also, dass die kürzeste Entfernung von einem Quellknoten zu einem Zielknoten besteht. Dies schlägt nur bei negativen Zyklen fehl.

Das ist richtig. Floyd-Warshall ist ein Beispiel für einen All-Pair-Shortest-Path-Algorithmus , der die kürzesten Pfade zwischen jedem Knotenpaar berechnet . Ein weiteres Beispiel ist "Führen Sie für jeden Knoten v Dijkstra mit v als Quellknoten aus". Es gibt mehrere andere.

Bellman-Ford wird wie Dijkstra verwendet, wenn es nur eine Quelle gibt. Dies kann mit negativen Gewichten umgehen und funktioniert genauso wie bei Floyd-Warshall mit Ausnahme einer Quelle, oder?

$O(V^3)$$O(V^2E)$$O(VE)$

Weitere Informationen finden Sie in Ihrem Lieblingslehrbuch für Algorithmen. (Sie haben ein Lieblingslehrbuch für Algorithmen, nicht wahr?)

Alle drei Algorithmen werden in den Vorlesungsfolien von Prof. Jaehyun Park (Stanford University) behandelt. Hier ist der Link Shortest Path Algorithms

Das Wikipedia-Seite zum Problem des kürzesten Pfades beschreibt zwei verschiedene Probleme: SSSP und APSP.

Single Source Shortest Path (SSSP):

• Dijkstra-Algorithmus: Löst das Problem des kürzesten Pfads aus einer Hand.
• • Einschränkungen: Nur negative Kanten können nicht verarbeitet werden.
• • Nicht gewichtete Grafiken: Dijkstra ist das gleiche wie BFS.

• Bellman-Ford-Algorithmus: Behebt das Single-Source-Problem, wenn die Kantengewichte möglicherweise negativ sind. Dies ist eine Verbesserung gegenüber Dijkstra, wo nun auch negative Gewichte verarbeitet werden können.

Alle paar kürzester Weg (APSP):

• Floyd-Warshall-Algorithmus: Löst die kürzesten Wege aller Paare. Behandelt sowohl positive als auch negative Flanken.
• • Einschränkungen: Negative Zyklen können nicht verarbeitet werden.

Daher ist Floyd-Warshall nicht dasselbe wie BFS, obwohl die zugrunde liegende Methodik dieselbe ist, nämlich die dynamische Programmierung.

Vielleicht sollte dies eher ein Kommentar als eine Antwort sein, aber es ist eine Unterscheidung zwischen diesen Algorithmen, die andere Antworten nicht erwähnen.

Die Leute neigen dazu, Floyds Algorithmus Floyd-Warshall zu nennen , aber Floyds und Warshalls Algorithmen sind nicht die gleichen.

$O(1)$$O(n^2)$