Dijkstra-Algorithmus

Ihr Routenplaner kennt den schnellsten Weg von Ihrer Haustür fast überallhin. Im Kern dieser Idee steckt ein Algorithmus, den Edsger Dijkstra 1956 in etwa zwanzig Minuten ausgearbeitet hat: vom Start aus nach außen wachsen und immer zuerst den nächstgelegenen Ort fertig machen.

Ein Graph, dessen Kanten Längen haben, mit den fertigen Knoten nahe dem Start in Grün, einem Baum kürzester Wege und einer darunter gezeichneten Prioritätswarteschlange
Ein Graph, dessen Kanten Längen haben, mit den fertigen Knoten nahe dem Start in Grün, einem Baum kürzester Wege und einer darunter gezeichneten Prioritätswarteschlange

Die Idee

Stellen Sie sich Orte vor, die durch unterschiedlich lange Straßen verbunden sind. Die Frage lautet: Was ist der kürzeste Weg von meinem Ort zu jedem anderen? Die Breitensuche beantwortet sie, wenn jede Straße gleich zählt, doch hier kann eine Route mit mehr Straßen kürzer sein. Der Dijkstra-Algorithmus speichert für jeden Ort den kürzesten bisher gefundenen Abstand und lässt eine Region von Orten mit sicherem Abstand wachsen, indem er immer den nächstgelegenen Ort hinzunimmt, der noch nicht sicher ist.

Schritt für Schritt

Der Start bekommt den Abstand 0, jeder andere Knoten unendlich. Der Start kommt in eine Prioritätswarteschlange, eine Warteschlange, die immer den Knoten mit dem kleinsten Abstand herausgibt. Dieser Knoten wird genommen; sein Abstand ist jetzt endgültig. Für jeden Nachbarn, der nicht endgültig ist, wird der Abstand über diesen Knoten berechnet: sein Abstand plus die Länge der Kante. Ist das kürzer als der bisherige Abstand des Nachbarn, wird dieser gesenkt, der Knoten wird als Weg dorthin gemerkt, und der Nachbar kommt in die Warteschlange. Das nennt man Relaxation einer Kante. Das wiederholt sich, bis die Warteschlange leer ist oder bis das Ziel aus ihr genommen wird.

Ein Beispiel

Nehmen wir die Kanten A–B mit Länge 4, A–C 1, B–C 2, B–D 1, C–D 5 und D–E 3 und starten bei A. Wird A genommen, bekommt B den Abstand 4 und C den Abstand 1. C ist am nächsten, also ist es mit 1 endgültig; über C sinkt B auf 1 + 2 = 3, und D bekommt 1 + 5 = 6. Jetzt ist B am nächsten, endgültig mit 3, und über B sinkt D auf 3 + 1 = 4. D ist mit 4 endgültig und gibt E 4 + 3 = 7. Der kürzeste Weg von A nach E ist also A → C → B → D → E mit Länge 7, obwohl A → B → D → E weniger Kanten nutzt und Länge 8 hat.

Warum er korrekt ist

Angenommen, Knoten X ist der nächstgelegene in der Warteschlange, mit Abstand d. Jeder andere Weg vom Start zu X muss die Region der endgültigen Knoten irgendwann verlassen, und der erste Knoten, den er außerhalb dieser Region erreicht, liegt in der Warteschlange, ist also schon mindestens d entfernt. Der Rest des Weges kann ihn nicht verkürzen, weil keine Kante negativ ist. Also ist d der kürzeste Abstand zu X. Mit einer negativen Kante gilt dieses Argument nicht mehr; dann nimmt man den Bellman–Ford-Algorithmus, der jede Kante immer wieder relaxiert.

Geschichte und Anwendungen

Edsger W. Dijkstra entwarf den Algorithmus 1956, um einen neuen Computer vorzuführen, die ARMAC in Amsterdam, indem er Routen zwischen niederländischen Städten fand, und veröffentlichte ihn 1959. Dieselbe Idee steckt, mit einer geschickteren Warteschlange, in Routenplanern und in Routing-Protokollen des Internets wie OSPF und IS-IS, die den kürzesten Weg für Daten zwischen Routern berechnen. Die A*-Suche fügt eine Schätzung der noch verbleibenden Strecke hinzu, so kann sie auf das Ziel zusteuern und muss weniger Knoten betrachten.

Edsger W. Dijkstra an der Tafel
Edsger W. Dijkstra an der Tafel

Selbst ausprobieren

Öffnen Sie die App und drücken Sie Schritt. Die Zahlen auf den Kanten sind ihre Längen, und die Zahl auf jedem Knoten ist sein bisheriger Abstand. Knoten in der Warteschlange sind blau, endgültige Knoten grün, und die Warteschlange unter dem Graphen listet sie mit ihren Abständen auf, die nächstgelegenen zuerst. Achten Sie auf die Momente, in denen ein Abstand sinkt, weil sich eine länger wirkende Route als kürzer erweist, und wählen Sie ein Ziel, um zu sehen, wie die Suche stoppt, sobald das Ziel endgültig ist.

Häufig gestellte Fragen

Welche Zeitkomplexität hat der Dijkstra-Algorithmus?

Das hängt von der Prioritätswarteschlange ab. Mit einer einfachen Liste ist sie O(V²) bei V Knoten; mit einem binären Heap O((V + E) log V) bei E Kanten; mit einem Fibonacci-Heap O(E + V log V), wie Michael Fredman und Robert Tarjan 1984 zeigten.

Kann der Dijkstra-Algorithmus mit negativen Kantengewichten umgehen?

Nein. Er geht davon aus, dass sich der Abstand eines Knotens nicht mehr verbessern kann, sobald der Knoten der nächstgelegene in der Warteschlange ist, und eine negative Kante kann genau das verletzen. Nehmen Sie für Graphen mit negativen Kanten den Bellman–Ford-Algorithmus.

Findet der Dijkstra-Algorithmus den Weg zu jedem Knoten?

Ja. Bis zum Ende ausgeführt, liefert er den kürzesten Abstand vom Start zu jedem erreichbaren Knoten, und die gemerkten Knoten bilden einen Baum kürzester Wege. Wird nur ein Weg gebraucht, spart es Arbeit, früh aufzuhören, sobald das Ziel endgültig ist.

Wie hängt der Dijkstra-Algorithmus mit A* zusammen?

Die A*-Suche ist der Dijkstra-Algorithmus mit einem Hinweis: Sie ordnet die Warteschlange nach dem bisherigen Abstand plus einer Schätzung der noch verbleibenden Strecke, etwa der Luftlinie auf einer Karte. Mit einer guten Schätzung findet sie denselben kürzesten Weg und betrachtet dabei weit weniger Knoten.

Bereit, es auszuprobieren?

Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.

Dijkstra-Algorithmus ausprobieren