Dijkstra -Algorithmus
![]() Dijkstra Algorithmus, um den kürzesten Weg zwischen zu finden a und b. Es wählt den nicht besuchten Scheitelpunkt mit der niedrigsten Entfernung aus, berechnet den Abstand durch ihn für jeden nicht besuchten Nachbarn und aktualisiert die Entfernung des Nachbarn, falls kleiner. Mark besuchte (auf rot eingestellt), wenn er mit Nachbarn fertig ist. | |
Klasse | Suchalgorithmus Gieriger Algorithmus Dynamische Programmierung[1] |
---|---|
Datenstruktur | Graph Normalerweise verwendet mit Prioritätswarteschlange/Haufen zur Optimierung[2][3] |
Schlimmsten Fall Leistung | [3] |
Dijkstra -Algorithmus (/ˈdaɪkstrəz/ DEICH-strəz) ist ein Algorithmus für das Finden der kürzeste Wege zwischen Knoten in einem Graph, was zum Beispiel darstellen kann, Straßennetzwerke. Es wurde von konzipiert von Informatiker Edsger W. Dijkstra 1956 und drei Jahre später veröffentlicht.[4][5][6]
Der Algorithmus existiert in vielen Varianten. Der ursprüngliche Algorithmus von Dijkstra fand den kürzesten Weg zwischen zwei gegebenen Knoten.[6] Eine häufigere Variante behebt jedoch einen einzelnen Knoten als "Quell" -Knoten und findet die kürzesten Pfade von der Quelle zu allen anderen Knoten im Diagramm, wobei er eine erzeugt Kürzester Pfadbaum.
Für einen bestimmten Quellknoten im Diagramm findet der Algorithmus den kürzesten Weg zwischen diesem Knoten und jedem anderen.[7]: 196–206 Es kann auch verwendet werden, um die kürzesten Pfade von einem einzelnen Knoten zu einem einzelnen Zielknoten zu finden, indem der Algorithmus gestoppt wird, sobald der kürzeste Pfad zum Zielknoten bestimmt wurde. Wenn beispielsweise die Knoten des Diagramms Städte darstellen und die Kosten für Kantenpfad zu Fahrabständen zwischen Städtenpaaren repräsentieren, die durch eine direkte Straße verbunden sind (zum Einfachheit halber, ignorieren Sie rote Licht um den kürzesten Weg zwischen einer Stadt und allen anderen Städten zu finden. Eine weit verbreitete Anwendung von kürzesten Pfadalgorithmen ist das Netzwerk Routing -Protokolle, vor allem Is-is (Zwischensystem zum Zwischensystem) und OSPF (Öffne den kürzesten Weg zuerst). Es ist auch als als beschäftigt Subroutine in anderen Algorithmen wie z. Johnsons.
Der Dijkstra -Algorithmus verwendet Etiketten, die positive Ganzzahlen oder reelle Zahlen sind, die sind total bestellt. Es kann verallgemeinert werden, um Etiketten zu verwenden, die sind teilweise bestellt, vorausgesetzt, die nachfolgenden Beschriftungen (eine nachfolgende Etikett wird beim Überqueren einer Kante erzeugt) sind monoton nicht dekretierend. Diese Generalisierung wird als generischer Dijkstra-Kürzeste-Pfad-Algorithmus bezeichnet.[8]
Der Algorithmus von Dijkstra verwendet eine Datenstruktur zum Speichern und Abfragen von Teillösungen, die nach Entfernung vom Start sortiert werden. Während der ursprüngliche Algorithmus a verwendet MIN-Prioritätswarteschlange und rennt herein Zeit (wo ist die Anzahl der Knoten und ist die Anzahl der Kanten), es kann auch in implementiert werden mit einem Array. Die Idee dieses Algorithmus ist auch in gegeben Leyzorek et al. 1957. Fredman & Tarjan 1984 vorschlagen mit a Fibonacci Heap Warteschlange zur Optimierung der Laufzeitkomplexität zu minriorität . Das ist asymptotisch die am schnellsten bekannte Single-Source Kürzester Pfadalgorithmus für willkürliche Regie Graphen mit unbegrenzten nicht negativen Gewichten. Spezialfälle (z. Spezialvarianten. Außerdem, wenn die Vorverarbeitung zulässig ist, Algorithmen wie z. Kontraktion hierarchien Kann bis zu sieben Größenordnungen schneller sein.
In einigen Bereichen, künstliche Intelligenz Insbesondere der Algorithmus von Dijkstra oder eine Variante davon ist bekannt als Einheitliche Kostensuche und als Instanz der allgemeineren Idee von formuliert Best-First-Suche.[9]
Geschichte
Was ist der kürzeste Weg zu reisen Rotterdam zu Groningenim Allgemeinen: Von der gegebenen Stadt zu gegebener Stadt. Es ist der Algorithmus für den kürzesten Weg, was ich in ungefähr zwanzig Minuten entworfen habe. Eines Morgens kaufte ich ein Amsterdam Mit meinem jungen Verlobten und müde setzten wir uns auf die Café -Terrasse, um eine Tasse Kaffee zu trinken, und ich dachte nur darüber nach, ob ich das tun konnte, und ich entwarf dann den Algorithmus für den kürzesten Weg. Wie gesagt, es war eine 20-minütige Erfindung. Tatsächlich wurde es im Jahr 59, drei Jahre später, veröffentlicht. Die Veröffentlichung ist immer noch lesbar, sie ist in der Tat ganz schön. Einer der Gründe, warum es so schön ist, war, dass ich es ohne Bleistift und Papier entworfen habe. Ich erfuhr später, dass einer der Vorteile des Entwerfens ohne Bleistift und Papier darin besteht, dass Sie fast gezwungen sind, alle vermeidbaren Komplexitäten zu vermeiden. Schließlich wurde dieser Algorithmus zu meinem großen Erstaunen, einem der Eckpfeiler meines Ruhmes.
-Edsger Dijkstra, in einem Interview mit Philip L. Frana, Kommunikation der ACM, 2001[5]
Dijkstra dachte über das kürzeste Wegproblem nach, wenn er am Arbeiten arbeitete Mathematisches Zentrum in Amsterdam 1956 als Programmierer, um die Funktionen eines neuen Computers namens ARMAC zu demonstrieren.[10] Sein Ziel war es, sowohl ein Problem als auch eine Lösung (die vom Computer erzeugt werden würde) zu wählen, die nicht berechnende Menschen verstehen konnten. Er entwarf den kürzesten Pfadalgorithmus und implementierte ihn später für ARMAC für eine leicht vereinfachte Transportkarte von 64 Städten in den Niederlanden (64, so dass 6 Bit ausreichen, um die Stadtnummer zu kodieren).[5] Ein Jahr später stieß er auf ein weiteres Problem von Hardware -Ingenieuren, die am nächsten Computer des Instituts arbeiteten: Minimieren Sie die Menge an Draht, die zum Anschließen der Stifte auf der Rückseite der Maschine erforderlich ist. Als Lösung entdeckte er den Algorithmus als bekannt als als Prims minimaler Spannungsbaumalgorithmus (früher bekannt zu Jarníkund auch wiederentdeckt von Prim).[11][12] Dijkstra veröffentlichte 1959 den Algorithmus, zwei Jahre nach Prim und 29 Jahren nach Jarník.[13][14]
Algorithmus

Lassen Sie den Knoten, bei dem wir anfangen, das genannt zu werden Anfangsknoten. Lasst den Entfernung des Knotens Y die Entfernung von der Anfangsknoten zu Y. Der Algorithmus von Dijkstra wird zunächst mit unendlichen Entfernungen beginnen und versuchen, sie Schritt für Schritt zu verbessern.
- Markieren Sie alle Knoten nicht besucht. Ein ... kreieren einstellen von allen nicht besuchten Knoten, die die genannt werden nicht besuchter Set.
- Jedem Knoten a zuweisen vorläufige Entfernung Wert: Stellen Sie es für unseren ersten Knoten und für alle anderen Knoten auf Null ein. Während des Laufs des Algorithmus der vorläufige Abstand eines Knotens v ist die Länge des kürzesten Weges, der bisher zwischen dem Knoten entdeckt wurde v und die beginnend Knoten. Da ein anderer Scheitelpunkt anfangs kein Pfad bekannt ist als die Quelle selbst (was ein Pfad von Länge Null ist), werden alle anderen vorläufigen Abstände zunächst auf unendlich eingestellt. Stellen Sie den Anfangsknoten als Strom ein.[15]
- Betrachten Sie für den aktuellen Knoten alle seine nicht besuchten Nachbarn und berechnen Sie ihre vorläufigen Entfernungen durch den aktuellen Knoten. Vergleichen Sie die neu berechnete vorläufige Entfernung mit dem derzeit dem Nachbarn zugewiesenen und weisen Sie ihm die kleinere zu. Zum Beispiel, wenn der aktuelle Knoten A ist mit einer Entfernung von 6 markiert und die Kante verbindet es mit einem Nachbarn B hat Länge 2, dann der Abstand zu B durch A ist 6 + 2 = 8. Wenn B zuvor mit einer Entfernung von mehr als 8 markiert wurde, ändern Sie ihn auf 8. Andernfalls wird der aktuelle Wert aufbewahrt.
- Wenn wir unter Berücksichtigung aller nicht besuchten Nachbarn des aktuellen Knotens fertig sind, markieren Sie den aktuellen Knoten wie besucht und entfernen Sie ihn aus dem nicht besuchten Satz. Ein besuchter Knoten wird nie wieder überprüft (dies ist im Zusammenhang mit dem Verhalten in Schritt 6 gültig und optimal: dass die nächsten Knoten immer in der Reihenfolge der kleinsten Entfernung zu sein werden Anfangsknoten Erstens 'so würden alle Besuche danach eine größere Entfernung haben).
- Wenn der Zielknoten besucht wurde (bei der Planung einer Route zwischen zwei spezifischen Knoten) oder wenn der kleinste vorläufige Abstand zwischen den Knoten im nicht besuchten Satz unendlich ist (bei der Planung eines vollständigen Durchgangs; und verbleibende nicht besuchte Knoten), dann stoppen Sie. Der Algorithmus ist beendet.
- Wählen Sie ansonsten den nicht besuchten Knoten aus, der mit der kleinsten vorläufigen Entfernung markiert ist, ihn als neue festlegen Stromknoten, und gehen Sie zurück zu Schritt 3.
Bei der Planung einer Route ist es nicht erforderlich, zu warten, bis der Zielknoten wie oben "besucht" ist: Der Algorithmus kann anhalten, sobald der Zielknoten die kleinste vorläufige Entfernung zwischen allen "nicht besuchten" Knoten hat (und daher so ausgewählt werden kann wie die Nächster "Strom").
Beschreibung
Angenommen, Sie möchten das finden kürzester Weg zwischen zwei Schnittpunkte auf einer Stadtkarte: a Startpunkt und ein Ziel. Der Algorithmus von Dijkstra markiert zunächst die Entfernung (vom Ausgangspunkt) zu jeder anderen Kreuzung auf der Karte mit Unendlichkeit. Dies wird nicht impliziert, dass es eine unendliche Entfernung gibt, sondern zu beachten, dass diese Kreuzungen noch nicht besucht wurden. Einige Varianten dieser Methode lassen die Entfernungen der Kreuzungen unbeschrieben. Wählen Sie nun die aus Stromkreuzung Bei jeder Iteration. Für die erste Iteration wird die aktuelle Kreuzung der Ausgangspunkt sein, und der Abstand zu ihm (das Etikett der Kreuzung) wird sein Null. Für nachfolgende Iterationen (nach dem ersten) wird die aktuelle Kreuzung a sein Nahte unbesetzte Kreuzung bis zum Ausgangspunkt (dies ist leicht zu finden).
Von der aktuellen Kreuzung, aktualisieren Die Entfernung zu jeder nicht besuchten Kreuzung, die direkt mit ihm verbunden ist. Dies geschieht durch die Bestimmung der Summe der Entfernung zwischen einer nicht besuchten Kreuzung und dem Wert der aktuellen Kreuzung und dann Wiedergutmachung Der nicht besuchte Kreuzung mit diesem Wert (der Summe), wenn er geringer ist als der aktuelle Wert der nicht besuchten Kreuzung. Tatsächlich ist der Schnittpunkt neu reflektiert, wenn der Weg zum Stromkreuz kürzer ist als die zuvor bekannten Pfade. Markieren Sie die Straße mit einem Pfeil, der auf die reverse Kreuzung zeigt, um die kürzeste Pfadidentifikation zu ermöglichen, wenn Sie sie beschriften/neu zu veranlassen, und alle anderen zu löschen, die darauf hinweisen. Nachdem Sie die Entfernungen zu jedem aktualisiert haben benachbarte Kreuzungmarkieren die aktuelle Kreuzung als hat besucht und wählen Sie eine nicht besuchte Kreuzung mit minimaler Entfernung (vom Startpunkt) oder der niedrigsten Etikette als aktuelle Kreuzung. Schnittpunkte, die als besucht gekennzeichnet sind, werden mit dem kürzesten Weg vom Ausgangspunkt zu ihm gekennzeichnet und werden nicht überarbeitet oder zurückgegeben.
Setzen Sie diesen Prozess der Aktualisierung der benachbarten Kreuzungen mit den kürzesten Entfernungen, markieren Sie die aktuelle Kreuzung als besucht und wechseln Sie zu einer unaufgelegten Kreuzung, bis Sie das Ziel wie besucht markiert haben. Sobald Sie das Ziel als besucht gekennzeichnet haben (wie es bei jeder besuchten Kreuzung der Fall ist), haben Sie den kürzesten Weg zum Startpunkt vom Startpunkt festgelegt und können Verfolgen Sie Ihren Weg zurück, um den Pfeilen umgekehrt zu folgen. In den Implementierungen des Algorithmus erfolgt dies normalerweise (nachdem der Algorithmus den Zielknoten erreicht hat), indem sie den Eltern der Knoten vom Zielknoten bis zum Startknoten folgen. Deshalb verfolgen wir auch die Eltern jedes Knotens.
Dieser Algorithmus unternimmt keinen Versuch der direkten "Erforschung" zum Ziel, wie man es erwarten könnte. Die einzige Überlegung bei der Bestimmung der nächsten "Strom" -Knuspinktion ist vielmehr der Abstand vom Ausgangspunkt. Dieser Algorithmus erweitert sich daher vom Startpunkt nach außen und betrachtet interaktiv jeden Knoten, der in Bezug auf die kürzeste Pfadentfernung näher ist, bis er das Ziel erreicht. Wenn dies auf diese Weise verstanden wird, ist klar, wie der Algorithmus notwendigerweise den kürzesten Weg findet. Es kann jedoch auch eine der Schwächen des Algorithmus zeigen: seine relative Langsamkeit in einigen Topologien.
Pseudocode
Im Folgenden Pseudocode Algorithmus, distieren ist ein Array, das die aktuellen Entfernungen von der enthält Quelle zu anderen Eckpunkten, d.h. dist [u] ist der aktuelle Abstand von der Quelle zum Scheitelpunkt u. Das vorläufig Array enthält Zeiger auf vorherige Hop-Knoten auf dem kürzesten Pfad von der Quelle zum gegebenen Scheitelpunkt (entsprechend ist es das NEXT-HOP auf dem Pfad aus der gegebene Scheitelpunkt zu die Quelle). Der Code u ← Scheitelpunkt in Q mit min dist [u], sucht nach dem Scheitelpunkt u im Scheitelpunktsatz Q das hat am wenigsten dist [u] Wert. Graph.edges (u, v) Gibt die Länge des Randes zurück (d. H. Der Abstand zwischen den beiden Nachbarnoten) u und v. Die Variable Alt In Zeile 14 ist die Länge des Pfades vom Wurzelknoten zum Nachbarknoten v Wenn es durchgehen würde u. Wenn dieser Pfad kürzer ist als der aktuelle kürzeste Weg für aufgezeichnet v, dieser aktuelle Pfad wird dadurch ersetzt Alt Weg.[7]

1 Funktion Dijkstra (Graph, Quelle): 2 3 für jeden Scheitel v in Graph.vertices: 4 dist [v] ← Infinity 5 prev [v] ← undefined 6 addieren v zu Q 7 dist [Quelle] ← 0 8 9 während Q ist nicht leer: 10 u ← Scheitelpunkt in Q mit min dist [u] 11 entfernen Sie u aus Q 12 13 für jeden Nachbar v von u immer noch in Q: 14 Alt ← dist [u] + Graph.edges (u, v) fünfzehn wenn Alt < dist[v] und dist [u] ist nicht unendlich: 16 dist [v] ← Alt 17 prec [v] ← u 18 19 Rückkehr dist [], prev []
Wenn wir nur an einem kürzesten Weg zwischen Scheitelpunkten interessiert sind Quelle und ZielWir können die Suche nach Zeile 10 beenden, wenn u = Ziel. Jetzt können wir den kürzesten Weg lesen Quelle zu Ziel durch umgekehrte Iteration:
1 S ← leere Sequenz 2 u ← Ziel 3 wenn vorher [u] ist definiert oder u = Quelle: // Mach etwas nur, wenn der Scheitelpunkt erreichbar ist 4 während u ist definiert: // Konstruieren Sie den kürzesten Weg mit einem Stapel s 5 Einfügen u am Anfang von S // Schieben Sie den Scheitelpunkt auf den Stapel 6 u ← prev [u] // Überqueren Sie von Ziel zu Quelle
Jetzt Sequenz S ist die Liste der Scheitelpunkte, die einen der kürzesten Wege ausmachen? Quelle zu Ziel, oder die leere Sequenz, wenn kein Weg vorhanden ist.
Ein allgemeineres Problem wäre, die kürzesten Wege zwischen den kürzesten Wegen zu finden Quelle und Ziel (Es kann verschiedene unterschiedliche Länge geben). Dann speichern Sie dann in jedem Eintrag von nur einen einzelnen Knoten vorher [] Wir würden alle Knoten speichern, die den Entspannungszustand erfüllen. Zum Beispiel wenn beide r und Quelle verbunden mit Ziel und beide liegen auf verschiedenen kürzesten Wegen durch Ziel (Da die Kantenkosten in beiden Fällen gleich sind), würden wir beide hinzufügen r und Quelle zu vorher [Ziel]. Wenn der Algorithmus abgeschlossen ist, vorher [] Die Datenstruktur beschreibt tatsächlich einen Diagramm, der eine Teilmenge des Originalgraps mit einigen entfernten Kanten ist. Die wichtigste Eigenschaft ist, dass, wenn der Algorithmus mit einem Startknoten ausgeführt wurde, jeder Pfad von diesem Knoten zu einem anderen Knoten im neuen Diagramm der kürzeste Pfad zwischen diesen Knoten im ursprünglichen Diagramm und alle Pfade dieser Länge von sein Die Originalgrafik wird im neuen Diagramm vorhanden sein. Um all diese kürzesten Wege zwischen zwei gegebenen Knoten tatsächlich zu finden, würden wir einen Pfad -Finding -Algorithmus in der neuen Grafik verwenden, wie z. Tiefe-First-Suche.
Verwenden einer vorrangigen Warteschlange
Eine Warteschlange zur Minimierung ist ein abstrakter Datentyp, der 3 grundlegende Vorgänge liefert: add_with_priority (), Abnahme_Priority () und extract_min (). Wie bereits erwähnt, kann die Verwendung einer solchen Datenstruktur zu schnelleren Rechenzeiten als die Verwendung einer Basiswarteschlange führen. Vor allem, Fibonacci Heap (Fredman & Tarjan 1984) oder Brodalwarteschlange Bieten Sie optimale Implementierungen für diese 3 Operationen an. Da der Algorithmus etwas anders ist, erwähnen wir ihn auch hier im Pseudocode:
1 Funktion Dijkstra (Graph, Quelle): 2 dist [Quelle] ← 0 // Initialisierung 3 4 Erstellen Sie Scheitelpunkte Prioritätswarteschlange Q 5 Q.add_with_priority (Quelle, dist [Quelle]) 6 7 für jeden Scheitel v in Graph.vertices: 8 wenn v ≠ Quelle 9 dist [v] ← Unendlichkeit // Unbekannte Entfernung von Quelle nach v 10 prec [v] ← undefiniert // Vorgänger von v 11 12 Q.add_with_priority (v, dist [v]) 13 14 15 während Q ist nicht leer: // die Hauptschleife 16 u ← Q.extract_min () // den besten Scheitelpunkt entfernen und zurückgeben 17 für jeden Nachbar v von u: // nur v, die noch in q sind 18 Alt ← dist [u] + Graph.edges (u, v) 19 wenn Alt < dist[v] und dist [u] ist nicht unendlich: 20 dist [v] ← Alt 21 prec [v] ← u 22 Q.decrease_priority (v, Alt) 23 24 Rückkehr Dist, Prev
Anstatt die Prioritätswarteschlange mit allen Knoten in der Initialisierungsphase zu füllen, ist es auch möglich, sie nur zu initialisieren, um nur zu enthalten Quelle; Dann im Inneren der Wenn Alt <dist [v]
Block, die Abnahme_Priority () wird ein add_with_priority () Operation Wenn der Knoten noch nicht in der Warteschlange ist.[7]: 198
Eine weitere Alternative besteht darin, die vorrangige Warteschlange bedingungslos Knoten hinzuzufügen und stattdessen nach der Extraktion zu überprüfen, ob noch keine kürzere Verbindung gefunden wurde. Dies kann durchgeführt werden, indem zusätzlich die zugehörige Priorität extrahiert werden p
aus der Warteschlange und nur weiter verarbeiten Wenn p == dist [u]
im Inneren Während Q nicht leer ist
Schleife. [16]
Diese Alternativen können vollständig Array-basierte Prioritätswarteschlangen ohne Abnahme der Funktionalität verwenden, die in der Praxis noch schnellere Rechenzeiten erreichen. Es wurde jedoch festgestellt, dass der Leistungsunterschied für dichtere Graphen enger ist.[17]
Nachweis der Korrektheit
Der Nachweis des Algorithmus von Dijkstra wird durch Induktion auf der Anzahl der besuchten Knoten erstellt.
Invariante Hypothese: Für jeden Knoten v, dist [v] ist die kürzeste Entfernung von Quelle zu v Wenn Sie nur über besuchte Knoten oder unendlich reisen, wenn kein solcher Weg besteht. (Hinweis: Wir nehmen nicht an dist [v] ist die tatsächliche kürzeste Entfernung für nicht besuchte Knoten.)
Der Basisfall ist, wenn nur ein besuchter Knoten vorhanden ist, nämlich der anfängliche Knoten QuelleIn diesem Fall ist die Hypothese trivial.
Ansonsten nehmen die Hypothese für angenommen N-1 besuchte Knoten. In diesem Fall wählen wir eine Kante Vu wo u hat am wenigsten dist [u] von irgendwelchen nicht besuchten Knoten so, dass dist [u] = dist [v] + graph.edges [v, u]. dist [u] wird als kürzester Entfernung von angesehen Quelle zu u Denn wenn es einen kürzeren Weg gab, und wenn w war der erste nicht besuchte Knoten auf diesem Weg dann durch die ursprüngliche Hypothese dist [w] > dist [u] das schafft einen Widerspruch. Ebenso, wenn es einen kürzeren Weg zu gab u ohne nicht besuchte Knoten zu verwenden, und wenn der letzte Knoten auf diesem Pfad waren wdann hätten wir gehabt dist [u] = dist [w] + graph.edges [w, u], auch ein Widerspruch.
Nach der Verarbeitung u Es wird immer noch wahr sein, dass für jeden nicht besuchten Knoten w, dist [w] wird die kürzeste Entfernung von sein Quelle zu w Nur mit besuchten Knoten, denn wenn es einen kürzeren Weg gab, der nicht verläuft u Wir hätten es zuvor gefunden, und wenn es einen kürzeren Weg verwendete u Wir hätten es bei der Verarbeitung aktualisiert u.
Nachdem alle Knoten besucht werden, der kürzeste Weg von Quelle zu jedem Knoten v besteht daher nur aus besuchten Knoten dist [v] ist die kürzeste Entfernung.
Laufzeit
Grenzen der Laufzeit des Dijkstra -Algorithmus an einem Diagramm mit Kanten E und Eckpunkte V kann als Funktion der Anzahl der Kanten ausgedrückt werden, bezeichnet, bezeichnet und die Anzahl der Scheitelpunkte, bezeichnet , verwenden Big-o Notation. Die gebundene Komplexität hängt hauptsächlich von der Datenstruktur ab, die zur Darstellung des Satzes verwendet wird Q. Im Folgenden können Obergrenzen vereinfacht werden, weil ist für jedes Diagramm, aber diese Vereinfachung ignoriert die Tatsache, dass in einigen Problemen andere Obergrenzen eingeschaltet werden Kann halten.
Für jede Datenstruktur für den Scheitelpunktsatz QDie Laufzeit ist in[2]
wo und sind die Komplexität der Abnahme und Extrakt-Minimum Operationen in Q, beziehungsweise.
Die einfachste Version des Algorithmus von Dijkstra speichert den Scheitelpunktsatz Q als verknüpfte Liste oder Array und Kanten als Kanten Adjazenzliste oder Matrix. In diesem Fall ist Extract-Minimum einfach eine lineare Suche durch alle Scheitelpunkte in Q, also ist die Laufzeit .
Zum spärliche Grafikendas heißt Grafiken mit weit weniger als Kanten, der Algorithmus von Dijkstra kann effizienter implementiert werden, indem das Diagramm in Form von Adjazenzlisten gespeichert und ein verwendet wird selbstausgleichender binärer Suchbaum, Binärhaufen, Pairing Heap, oder Fibonacci Heap Als ein Prioritätswarteschlange Implementieren von minimalem extrahieren effizient. Um die Schritte für abnehmende Kee effizient aus durchzuführen Q Änderungen. Mit einem selbstausgleichenden binären Suchbaum oder eines binären Haufens erfordert der Algorithmus
Zeit im schlimmsten Fall (wo bezeichnet den binären Logarithmus ); Für angeschlossene Graphen kann diesmal gebunden sind zu vereinfacht werden zu . Das Fibonacci Heap verbessert dies um
Bei Verwendung von Binärhaufen die Durchschnittlicher Fall Die Zeitkomplexität ist niedriger als die schlimmste Fälle: Angenommen, die Kantenkosten werden unabhängig von einem gemeinsamen Zeugnis gezogen Wahrscheinlichkeitsverteilung, die erwartete Anzahl von Abnahme Operationen sind durch , eine totale Laufzeit von geben[7]: 199–200
Praktische Optimierungen und unendliche Graphen
In gemeinsamen Präsentationen des Dijkstra -Algorithmus werden zunächst alle Knoten in die Prioritätswarteschlange eingegeben. Dies ist jedoch nicht erforderlich: Der Algorithmus kann mit einer Prioritätswarteschlange beginnen, die nur einen Element enthält, und neue Elemente einfügen, wie sie entdeckt werden ist, verringern Sie seinen Schlüssel, andernfalls fügen Sie ihn ein).[7]: 198 Diese Variante hat die gleichen schlimmsten Grenzen wie die gemeinsame Variante, hält jedoch eine kleinere Prioritätswarteschlange in der Praxis bei, wodurch die Warteschlangenvorgänge beschleunigt werden.[9]
Wenn Sie nicht alle Knoten in einen Diagramm einfügen, können Sie den Algorithmus erweitern, um den kürzesten Pfad von einer einzelnen Quelle bis zum nächsten einer Reihe von Zielknoten auf unendlichen Graphen oder denjenigen zu finden, die zu groß sind, um sie im Speicher darzustellen. Der resultierende Algorithmus heißt Uniform-Kosten-Suche (UCS) in der Literatur zur künstlichen Intelligenz[9][18][19] und kann in Pseudocode als ausgedrückt werden
Verfahren Uniform_Cost_search (Start) ist Knoten ← Start Frontier ← Prioritätswarteschlange mit Knoten nur erweitert ← leerer Satz tun wenn Frontier ist leer dann Rückkehr Fehlerknoten ← Frontier.pop () wenn Knoten ist ein Zielzustand dann Rückkehr Lösung (Knoten) erweitert.Add (Knoten) für jeden der Nachbarn des Knotens n tun wenn n ist nicht erweitert und nicht in Grenze dann frontier.add (n)) sonst wenn n ist in Frontier mit höheren Kosten ersetzen vorhandenen Knoten durch n
Die Komplexität dieses Algorithmus kann auf alternative Weise für sehr große Grafiken ausgedrückt werden: wenn C* ist die Länge des kürzesten Pfades vom Startknoten bis zu einem beliebigen Knoten, der das Prädikat "Ziel" erfüllt, jede Kante hat zumindest gekostet εund die Anzahl der Nachbarn pro Knoten ist von begrenzt bund dann sind die schlimmsten Zeit- und Raumkomplexität des Algorithmus beide in O(b1+⌊C* ⁄ ε⌋).[18]
Weitere Optimierungen des Dijkstra-Algorithmus für den Einzelziel-Fall enthalten bidirektional Varianten, zielgerichtete Varianten wie die A* Algorithmus (sehen § Verwandte Probleme und Algorithmen), Graph-Beschneidung, um zu bestimmen, welche Knoten wahrscheinlich das mittlere Segment der kürzesten Pfade (Reichweite Routing) und hierarchische Zerlegung des Eingabestapels bilden, die sich verringern, die sich verringern s–t Routing mit einer Verbindung s und t zu ihrem jeweiligen "Transitknoten"Gefolgt von der kürzesten Path-Berechnung zwischen diesen Transitknoten unter Verwendung einer" Autobahn ".[20] Für eine optimale praktische Leistung bei bestimmten Problemen können Kombinationen solcher Techniken erforderlich sein.[21]
Spezialvarianten
Wenn die Lichtbogengewichte Small Ganzzahlen sind (begrenzt durch einen Parameter ), spezialisierte Warteschlangen, die diese Tatsache nutzen, können verwendet werden, um den Algorithmus von Dijkstra zu beschleunigen. Der erste Algorithmus dieses Typs war Dial's Algorithmus (Zifferblatt 1969) für Grafiken mit positiven Ganzzahlkantengewichten, die a verwendet Eimer -Warteschlange eine Laufzeit erhalten . Die Verwendung von a Van Emde Boas Baum Da die vorrangige Warteschlange die Komplexität zu (Ahuja et al. 1990). Eine weitere interessante Variante basiert auf einer Kombination aus einem neuen Radix Heap und der bekannte Fibonacci Heap läuft rechtzeitig (Ahuja et al. 1990). Schließlich sind die besten Algorithmen in diesem Sonderfall wie folgt. Der Algorithmus gegeben durch ((Thorup 2000) läuft herein Zeit und der Algorithmus gegeben durch ((Raman 1997) läuft herein Zeit.
Verwandte Probleme und Algorithmen
Die Funktionalität des ursprünglichen Algorithmus von Dijkstra kann mit einer Vielzahl von Modifikationen erweitert werden. Zum Beispiel ist es manchmal wünschenswert, Lösungen vorzustellen, die weniger als mathematisch optimal sind. Um eine Rangliste von weniger als optimalen Lösungen zu erhalten, wird zunächst die optimale Lösung berechnet. Eine einzelne Kante, die in der optimalen Lösung erscheint, wird aus dem Diagramm entfernt und die optimale Lösung für diesen neuen Diagramm wird berechnet. Jede Kante der ursprünglichen Lösung wird nacheinander unterdrückt und ein neuer kürzester Weg berechnet. Die Sekundärlösungen werden dann nach der ersten optimalen Lösung eingestuft und präsentiert.
Der Algorithmus von Dijkstra ist normalerweise das Arbeitsprinzip dahinter Link-State-Routing-Protokolle, OSPF und Is-is die häufigsten sein.
Im Gegensatz zu Dijkstra's Algorithmus die Bellman -.ford -Algorithmus Kann in Diagramme mit negativen Kantengewichten verwendet werden, solange das Diagramm nein enthält negativer Zyklus Erreichbar aus dem Quellscheitelpunkt s. Das Vorhandensein solcher Zyklen bedeutet, dass es keinen kürzesten Weg gibt, da das Gesamtgewicht jedes Mal niedriger wird, wenn der Zyklus durchquert wird. (In dieser Aussage geht davon aus, dass ein "Pfad" Eckpunkte wiederholen darf. Graphentheorie Das ist normalerweise nicht erlaubt. Im Theoretische Informatik Es ist oft erlaubt.) Es ist möglich, den Algorithmus von Dijkstra anzupassen, um negative Gewichtskanten zu bewältigen, indem es mit dem Bellman-Ford-Algorithmus kombiniert wird (um negative Kanten zu entfernen und negative Zyklen zu erkennen), ein solcher Algorithmus heißt Johnsons Algorithmus.
Das A* Algorithmus ist eine Verallgemeinerung des Dijkstra -Algorithmus, der die Größe des Untergraphen reduziert, der untersucht werden muss, wenn zusätzliche Informationen verfügbar sind, die eine niedrigere Grenze für die "Entfernung" zum Ziel liefert. Dieser Ansatz kann aus der Perspektive von betrachtet werden Lineares Programmieren: Es gibt eine natürliche Lineares Programm für die Berechnung kürzester Pfadeund Lösungen für seine Dual lineares Programm sind machbar, wenn und nur wenn sie a bilden konsequent heuristisch (ungefähr sprechen, da sich die Zeichenkonventionen von Ort zu Ort in der Literatur unterscheiden). Diese realisierbare duale / konsistente Heuristik definiert eine nicht negative reduzierte Kosten und A* betreibt im Wesentlichen den Algorithmus von Dijkstra mit diesen reduzierten Kosten. Wenn der Dual den schwächeren Zustand von erfüllt ZulässigkeitDann ist A* stattdessen eher dem Bellman -Ford -Algorithmus ähnlich.
Der Prozess, der den Algorithmus von Dijkstra zugrunde liegt gierig Prozess verwendet in Prims Algorithmus. Prims Zweck ist es, a zu finden Minimum Spanning Tree Das verbindet alle Knoten im Diagramm; Dijkstra befasst sich mit nur zwei Knoten. Prim's bewertet das Gesamtgewicht des Pfades nicht vom Startknoten, sondern nur die einzelnen Kanten.
Breite-First-Suche Kann als Spezialfall des Dijkstra-Algorithmus in ungewichteten Graphen angesehen werden, bei denen die vorrangige Warteschlange in eine FIFO-Warteschlange entgeegen.
Das Schnelle Marschmethode Kann als kontinuierliche Version des Dijkstra -Algorithmus angesehen werden, der die geodätische Entfernung auf einem Dreieck -Netz berechnet.
Dynamische Programmierperspektive
Von einem Dynamische Programmierung Sichtweise, der Algorithmus von Dijkstra ist ein aufeinanderfolgendes Näherungsschema Greifen Methode.[22][23][24]
Tatsächlich Erklärung von Dijkstra für die Logik hinter dem Algorithmus,[25] nämlich
Problem 2. Finden Sie den Pfad der minimalen Gesamtlänge zwischen zwei gegebenen Knoten und .
Wir verwenden die Tatsache, dass, wenn ist ein Knoten auf dem minimalen Weg von zu , Kenntnis der letzteren impliziert die Kenntnis des minimalen Weges von zu .
ist eine Umschreibung von Bellman berühmt Prinzip der Optimalität im Kontext des kürzesten Pfadproblems.
Anwendungen
Am wenigsten günstige Pfade werden zum Beispiel berechnet, um Spuren von Stromleitungen oder Ölleitungen festzulegen. Der Algorithmus wurde auch verwendet, um optimale Fernwände in Äthiopien zu berechnen und sie mit der Situation vor Ort zu kontrastieren.[26]
Siehe auch
- Ein* Suchalgorithmus
- Bellman -.ford -Algorithmus
- Euklidischer kürzester Weg
- Floyd -Warshall -Algorithmus
- Johnsons Algorithmus
- Längster Wegproblem
- Parallele All-Pairs-kürzester Pfadalgorithmus
Anmerkungen
- ^ Umstritten, siehe Moshe Sniedovich (2006). "Dijkstra's Algorithmus Revisited: The Dynamic Programming Connexion". Kontrolle und Kybernetik. 35: 599–620. und unter Teil.
- ^ a b Cormen et al. 2001
- ^ a b Fredman & Tarjan 1987
- ^ Richards, Hamilton. "Edsger Wybe Dijkstra". BIN. Turing Award. Verband für Rechenmaschinen. Abgerufen 16. Oktober 2017.
Im mathematischen Zentrum baute ein Großprojekt den Armac -Computer. Für seine offizielle Amtseinführung im Jahr 1956 entwickelte Dijkstra ein Programm, um ein Problem zu lösen, das für ein nichttechnisches Publikum interessant ist: Angesichts eines Straßennetzes, das Städte mit Städten verbindet, was ist die kürzeste Route zwischen zwei bestimmten Städten?
- ^ a b c Frana, Phil (August 2010). "Ein Interview mit Edsger W. Dijkstra". Kommunikation der ACM. 53 (8): 41–47. doi:10.1145/1787234.1787249.
- ^ a b Dijkstra, E. W. (1959). "Ein Hinweis zu zwei Problemen im Zusammenhang mit Diagrammen" (PDF). Numerische Mathematik. 1: 269–271. doi:10.1007/bf01386390. S2CID 123284777.
- ^ a b c d e Mehlhorn, Kurt; Sanders, Peter (2008). "Kapitel 10. Kürzeste Wege" (PDF). Algorithmen und Datenstrukturen: Die grundlegende Toolbox. Springer. doi:10.1007/978-3-540-77978-0. ISBN 978-3-540-77977-3.
- ^ Szcześniak, Ireneusz; Jajszczyk, Andrzej; Woźna-Szcześniak, Bożena (2019). "Generisches Dijkstra für optische Netzwerke". Journal of Optical Communications and Networking. 11 (11): 568–577. Arxiv:1810.04481. doi:10.1364/jocn.11.000568. S2CID 52958911.
- ^ a b c Felner, Ariel (2011). Positionspapier: Dijkstra -Algorithmus gegen einheitliche Kostensuche oder ein Fall gegen Dijkstra's Algorithmus. Proc. 4. int'l symp. Bei kombinatorischer Suche. In einem Routenfindungsproblem stellt Felner fest, dass die Warteschlange ein Faktor 500–600 kleiner sein kann und etwa 40% der Laufzeit dauert.
- ^ "Armac". Unbesungene Helden in der niederländischen Computergeschichte. 2007. archiviert von das Original am 13. November 2013.
- ^ Dijkstra, Edsger W.,, Reflexionen zu "Eine Notiz zu zwei Problemen im Zusammenhang mit Diagrammen (PDF)
- ^ Tarjan, Robert Endre (1983), Datenstrukturen und Netzwerkalgorithmen, CBMS_NSF Regional Conference Series in Applied Mathematics, Vol. 44, Gesellschaft für industrielle und angewandte Mathematik, p. 75,
Der dritte klassische Minimum -Spanning -Baum -Algorithmus wurde von Jarník entdeckt und von Prim und Dikstra wiederentdeckt; Es ist allgemein als Prims Algorithmus bekannt.
- ^ Prim, R.C. (1957). "Kürzeste Verbindungsnetzwerke und einige Verallgemeinerungen" (PDF). Glockensystem Technisches Journal. 36 (6): 1389–1401. Bibcode:1957BSTJ ... 36.1389p. doi:10.1002/j.1538-7305.1957.tb01515.x. Archiviert von das Original (PDF) am 18. Juli 2017. Abgerufen 18. Juli 2017.
- ^ V. Jarník: O Jistém problému minimálním [Über ein bestimmtes minimales Problem], Práce Moravské Přírodovědecke Společnosti, 6, 1930, S. 57–63. (im Tschech)
- ^ Gass, Saul; Fu, Michael (2013). Gass, Saul I; Fu, Michael C (Hrsg.). "Dijkstra -Algorithmus". Enzyklopädie der Operationsforschung und -managementwissenschaft. Springer. 1. doi:10.1007/978-1-4419-1153-7. ISBN 978-1-4419-1137-7 - über Springer Link.
- ^ Beobachten Sie das p < dist[u] kann niemals wegen des Updates halten dist [v] ← Alt Beim Aktualisieren der Warteschlange. Sehen https://cs.stackexchange.com/questions/118388/dijkstra-without-decrease-key zur Diskussion.
- ^ Chen, M.; Chowdhury, R. A.; Ramachandran, V.; Roche, D. L.; Tong, L. (2007). Priority Warteschlangen und Dijkstra-Algorithmus-UTCS Technischer Bericht TR-07-54-12. Oktober 2007 (PDF). Austin, Texas: Die Universität von Texas in Austin, Abteilung für Computerwissenschaften.
- ^ a b Russell, Stuart; Norvig, Peter (2009) [1995]. Künstliche Intelligenz: ein moderner Ansatz (3. Aufl.). Prentice Hall. S. 75, 81. ISBN 978-0-13-604259-4.
- ^ Manchmal auch Die am wenigsten günstige Suche: Nau, Dana S. (1983). "Experten Computersysteme" (PDF). Computer. IEEE. 16 (2): 63–85. doi:10.1109/mc.1983.1654302. S2CID 7301753.
- ^ Wagner, Dorothea; Willhalm, Thomas (2007). Geschwindigkeitstechniken für kürzeste Path-Berechnungen. STACS. S. 23–36.
- ^ Bauer, Reinhard; Delling, Daniel; Sanders, Peter; Schieferdecker, Dennis; Schulte, Dominik; Wagner, Dorothea (2010). "Hierarchische und zielgerichtete Geschwindigkeitstechniken für Dijkstra-Algorithmus kombinieren". J. Experimentelle Algorithmik. 15: 2.1. doi:10.1145/1671970.1671976. S2CID 1661292.
- ^ Sniedovich, M. (2006). "Dijkstra's Algorithmus Revisited: The Dynamic Programming Connexion" (PDF). Journal of Control and Cybernetics. 35 (3): 599–620. Online -Version des Papiers mit interaktiven Rechenmodulen.
- ^ Denardo, E.V. (2003). Dynamische Programmierung: Modelle und Anwendungen. Mineola, NY: Dover Publications. ISBN 978-0-486-42810-9.
- ^ Sniedovich, M. (2010). Dynamische Programmierung: Grundlagen und Prinzipien. Francis & Taylor. ISBN 978-0-8247-4099-3.
- ^ Dijkstra 1959, p. 270
- ^ Nyssen, J., Tesfaalem Ghebreyohannes, Hailemariam Meaza, Dondeyne, S., 2020. Erforschung einer mittelalterlichen afrikanischen Karte (Aksum, Äthiopien) - Wie passen historische Karten zur Topographie? In: De Ryck, M., Nyssen, J., Van Acker, K., Van Roy, W., Liber Amicorum: Philippe de Maeyer in Kaart. Wachtebeke (Belgien): University Press: 165-178.
Verweise
- Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "Abschnitt 24.3: Dijkstra -Algorithmus". Einführung in Algorithmen (Zweite Ausgabe). MIT Press und McGraw -Hill. S. 595–601. ISBN 0-262-03293-7.
- Dial, Robert B. (1969). "Algorithmus 360: Kürzester Wald mit topologischer Reihenfolge [h]". Kommunikation der ACM. 12 (11): 632–633. doi:10.1145/363269.363610. S2CID 6754003.
- Fredman, Michael Lawrence; Tarjan, Robert E. (1984). Fibonacci Heaps und ihre Verwendung in verbesserten Netzwerkoptimierungsalgorithmen. 25. jährliches Symposium für Grundlagen der Informatik. IEEE. S. 338–346. doi:10.1109/sfcs.1984.715934.
- Fredman, Michael Lawrence; Tarjan, Robert E. (1987). "Fibonacci Heaps und ihre Verwendung in verbesserten Netzwerkoptimierungsalgorithmen". Journal of the Association for Computing Machinery. 34 (3): 596–615. doi:10.1145/28869.28874. S2CID 7904683.
- Zhan, F. Benjamin; Noon, Charles E. (Februar 1998). "Kürzeste Pfadalgorithmen: Eine Bewertung mit realen Straßennetzwerken". Transportwissenschaft. 32 (1): 65–73. doi:10.1287/TRSC.32.1.65. S2CID 14986297.
- Leyzorek, M.; Gray, R. S.; Johnson, A. A.; Ladew, W. C.; Meaker, Jr., S. R.; Petry, R. M.; Seitz, R. N. (1957). Untersuchung von Modelltechniken - Erster Jahresbericht - 6. Juni 1956 - 1. Juli 1957 - Eine Studie über Modelltechniken für Kommunikationssysteme. Cleveland, Ohio: Case Institute of Technology.
- Knuth, D.E. (1977). "Eine Verallgemeinerung des Algorithmus von Dijkstra". Informationsverarbeitungsbriefe. 6 (1): 1–5. doi:10.1016/0020-0190 (77) 90002-3.
- Ahuja, Ravindra K.; Mehlhorn, Kurt; Orlin, James B.; Tarjan, Robert E. (April 1990). "Schnellere Algorithmen für das kürzeste Pfadproblem" (PDF). Journal of the ACM. 37 (2): 213–223. doi:10.1145/77600.77615. HDL:1721.1/47994. S2CID 5499589.
- Raman, Rajeev (1997). "Neuere Ergebnisse zum Problem der kürzesten Pfade mit Single-Source-Pfaden". Sigact News. 28 (2): 81–87. doi:10.1145/261342.261352. S2CID 18031586.
- Thorup, Mikkel (2000). "Auf RAM -Prioritätswarteschlangen". Siam Journal über Computing. 30 (1): 86–109. doi:10.1137/s0097539795288246. S2CID 5221089.
- Thorup, Mikkel (1999). "Ungelenkte Einzel-Source-kürzeste Wege mit positiven Ganzzahl-Gewichten in der linearen Zeit". Journal of the ACM. 46 (3): 362–394. doi:10.1145/316542.316548. S2CID 207654795.
Externe Links
- Oral History Interview mit Edsger W. Dijkstra, Charles Babbage Institute, Universität von Minnesota, Minneapolis
- Implementierung des Dijkstra -Algorithmus mit TDD, Robert Cecil Martin, Der saubere Code -Blog