Was ist der Unterschied zwischen dem „Floyd-Warshall-Algorithmus“ und „Dijkstra-Algorithmus“, und das ist die beste in einem Graphen des kürzesten Weg zu finden?Der beste kürzeste Weg Algorithmus
Ich brauche den kürzesten Weg zwischen allen Paaren in einem Netz zu berechnen und die Ergebnisse in einem Array speichern wie folgt:
**A B C D E**
A 0 10 15 5 20
B 10 0 5 5 10
C 15 5 0 10 15
D 5 5 10 0 15
E 20 10 15 15 0
Dijkstra Der Algorithmus ermittelt den kürzesten Pfad zwischen einem Knoten und jedem anderen Knoten im Diagramm. Sie würden es für jeden Knoten einmal ausführen. Gewichte müssen nicht negativ sein. Wenn nötig, müssen Sie die Werte in der Grafik zuerst normalisieren.
Floyd-Warshall berechnet die kürzesten Routen zwischen allen Knotenpaaren in einem einzigen Lauf! Zyklusgewichte müssen nicht negativ sein, und das Diagramm muss gerichtet sein (Ihr Diagramm ist nicht).
Johnson Der Algorithmus verwendet Dijkstra-Algorithmus, um alle Paare in einem einzigen Durchgang zu finden, und ist schneller für spärliche Bäume (siehe den Link für die Analyse).
Aus dem Wikipedia-Link zitieren Sie für Dijkstra: "Der Algorithmus findet den Pfad mit den niedrigsten Kosten zwischen diesem Knoten und ** jedem ** anderen Knoten" (meine Hervorhebung). Sie müssen es also nicht für jedes Scheitelpunktpaar, sondern nur für jeden Scheitelpunkt ausführen. –
thx Andreas, fixed – Will
Sie können einen ungerichteten Graphen in einen gerichteten Graphen umwandeln, indem Sie jede Kante uv durch zwei Kanten (u, v) und (v, u) mit demselben Gewicht ersetzen. Dann dürfte wohl Floyd-Warshall gut funktionieren? –
Floyd Warshall die Pfade zwischen allen Paaren von Scheitelpunkten finden, aber Dijkstra nur findet der Weg von einem Eckpunkt zu allen anderen.
Floyd Warshall ist O (| V |) und Dikstra ist O (| E | + | V | log | V |) aber du musst es V mal laufen lassen, um alle Paare zu finden, die a ergeben Komplexität von O (| E * V | + | V | log | V |) Ich denke. Dies bedeutet, dass es möglicherweise schneller ist, Dijsktra wiederholt als den FW-Algorithmus zu verwenden. Ich würde beide Ansätze ausprobieren und sehen, welche im aktuellen Fall am schnellsten ist.
Francis Haart Kommentar: "@Andreas Brinck, in einem vollständigen Diagramm, E = (V^2-V)/2, und Dijkstra wäre nicht schneller." –
Verwenden Sie den Floyd-Warshall-Algorithmus, wenn Sie den kürzesten Pfad zwischen Paaren von Eckpunkten finden möchten, da er eine (weit) höhere Laufzeit hat als der Dijkstra-Algorithmus.
Der Floyd-Warshall-Algorithmus hat eine Worst-Case-Leistung von O (| V |), wo als Dijkstra ein schlechter Fall Leistung von O hat (| E | + | V | log | V |)
Dijkstra findet den kürzesten Weg von nur einen Vertex, findet Floyd-Warshall zwischen alle von ihnen.
Dijkstra's ist hauptsächlich für die Suche nach kürzestem Paarpaaren, d. H. Von einem Knoten zu allen anderen Knoten, wo Floyd-Warshall der kürzeste Weg für alle Paare ist, d.h. der kürzeste Weg zwischen allen Knotenpaaren. Der Floyd-Warshall-Algorithmus hat eine Worst-Case-Performance von O (| V | 3), wobei Dijkstra's eine schlechtere Case-Performance von O (| E | + | V | log | V |) hat Auch Dijkstra's kann nicht für negative verwendet werden Gewichte (wir verwenden Bellmann Ford für das gleiche). aber für Floyd-Warshall können wir negative Gewichte verwenden, aber keine negativen Zyklen
In der Zwischenzeit sind bessere Algorithmen für das Single-Source-Shortest-Path-Problem bekannt. Ein praktisch relevanter ist ein derivation of Dijkstra's algorithm by Torben Hagerup. Der Algorithmus hat die gleiche Worst-Case-Komplexität wie Djikstra, aber im Durchschnitt ist die erwartete Laufzeit in der Größe des Graphen linear, was viel schneller ist als das reine Dijkstra. Die Idee des Algorithmus basiert auf der Idee, dass es nicht notwendig ist, immer die minimale Kante aus der Warteschlange abzufragen.Es ist möglich, eine Kante aus der Warteschlange abzufragen, deren Gewicht mal so groß ist wie das minimale Kantengewicht, wobei k eine Nummer größer ist 0. Selbst wenn eine solche Kante gewählt wird, findet der Algorithmus immer noch den kürzesten Weg.
aber der andere wurde geschlossen, vor allem wegen des schlechten Englisch des Benutzers, und eine der Lösungen nannte diese genau zwei Algorithmen als Alternativen. Wenn wir das als duplex abschließen, wie wird der Autor mehr über die vorherige Frage erfahren? Werden wir wirklich alle nett genug sein, um dort hinzugehen und dafür zu stimmen, wieder zu öffnen? – Will
hallo sorry, aber wollte ein Array-Beispiel in Bezug auf ein Bild hinzufügen, aber ich tat nicht – ricardo
danke, SilentGhost für die erneute Bearbeitung meiner Frage – ricardo