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

Question

Ich habe die drei studiert und ich mache meine Schlussfolgerungen von ihnen darunter. Könnte mir jemand sagen, ob ich sie genau verstanden habe oder nicht? Danke.

.

1. Dijkstra-Algorithmus wird nur verwendet, wenn Sie über eine einzige Quelle verfügen, und Sie möchten den kleinsten Pfad von einem Knoten zum anderen kennen, fehl jedoch in Fällen wie Dies

2. Floyd-Warshalls Algorithmus wird verwendet, wenn eines von allen Knoten eine Quelle sein kann, sodass Sie den kürzesten Abstand benötigen, um einen beliebigen Zielknoten von einem beliebigen Quellknoten zu erreichen. Dies versagt nur, wenn negative Zyklen vorhanden sind

(das ist der wichtigste. Ich meine, das ist derjenige, den ich am wenigsten sicher bin :)

3.Bellman-Ford wird wie Dijkstra's verwendet, wenn es nur eine Quelle gibt. Dies kann mit negativen Gewichten und sein Arbeiten mit der Floyd-Warshalls mit Ausnahme einer Quelle, rechts?

Wenn Sie einen Blick darauf werfen müssen, sind die entsprechenden Algorithmen (mit freundlicher Genehmigung Wikipedia):

bellman-ford:

generasacodicetagpre.

dijkstra:

generasacodicetagpre.

Floyd-Warshall:

generasacodicetagpre.

Answer 1

Sie sind korrekt über die ersten beiden Fragen, und über das Ziel der Floyd-Warshall (finden Sie die kürzesten Wege zwischen allen Paaren), jedoch nicht über die Beziehung zwischen Bellman-Ford und Floyd-Warshall: Beide Algorithmen verwenden die dynamische Programmierung an Finden Sie den kürzesten Pfad, aber fw ist nicht dasselbe mit dem Laufen von BF von jedem Startknoten an jeden anderen Knoten.

In BF ist die Frage: Was ist der kürzeste Pfad von der Quelle zum Ziel mit den meisten K-Schritten, und die Laufzeit ist o (e v). Wenn wir es an einen anderen Knoten ausführen würden, wäre die Laufzeit o (e v ^ 2).

In FW ist die Frage: Was ist der kürzeste Weg von I bis J bis k, für alle Knoten I, j, k. Dies führt zu O (V ^ 3) Laufzeit - besser als BF für jeden Startknoten (um einen Faktor von bis zu | V | für dichte Diagramme).

Eine weitere Note über negative Zyklen / Gewichte: Dijkstra kann einfach nicht die richtigen Ergebnisse angeben. BF und FW scheitern nicht - sie werden korrekt angeben, dass es keinen minimalen Gewichtspfad gibt, da das negative Gewicht unbegrenzt ist.

Answer 2

Single Source Kürzeste Wege:

Dijkstra-Algorithmus - kein negatives Gewicht erlaubt - o (e + vlg (v))

Bellman Ford Algorithmus - Negativgewicht ist erlaubt.Wenn jedoch ein negativer Zyklus vorliegt, erkennt Bellman Ford den -ve-Zyklus - O (ve)

gerichtetes azyklisches Diagramm - wie der Name vermuten lässt es nur für DAG-O (V + E)

funktionieren

Alle paar kürzeste Wege:

Dijkstra-Algorithmus - kein negatives Gewicht erlaubt - o (ve + v ^ 2lg (v))

Bellman Ford Algorithmus - O (V ^ 2e)

Matrix-Kettenmultiplikationsmethode -Complexität wie Bellman Ford Algorithmus

Floyd Warshall-Algorithmus -USES Dynamisches Programmierverfahren - Komplexität ist O (V ^ 3)