Dijkstra-Algorithmus einfach erklärt

Ein Graph besteht aus Knoten und Kanten. In einem kantengewichteten Graphen trägt jede Kante eine Zahl, zum Beispiel eine Streckenlänge. Der Dijkstra-Algorithmus berechnet einen kürzesten Pfad von einem gegebenen Startknoten zu einem der übrigen Knoten oder zu allen. Das klappt, sofern der Graph keine negativen Kantengewichte enthält.

Ein bekanntes Beispiel sind Routenplaner: Der Graph stellt das Verkehrswegenetz dar, und gesucht ist die kürzeste Route zwischen zwei Punkten. Die Kantengewichte dürfen dabei verschieden sein, später etwa 5 für S–A und 6 für S–B.

Willst du nur den Weg zu einem bestimmten Zielknoten, kannst du abbrechen, sobald der gesuchte Knoten an der Reihe ist. Du musst dann nicht alle Knoten besuchen. In einem unzusammenhängenden ungerichteten Graphen ist der Abstand zu Knoten unendlich, zu denen kein Pfad vom Startknoten aus existiert.

Haben alle Kanten dasselbe Gewicht, genügt für einen kürzesten Pfad schon die Breitensuche. Für Graphen mit negativen Kantengewichten gibt es den Bellman-Ford-Algorithmus, der mit negativen Kantengewichten umgehen kann.

Dijkstra gehört zu den Greedy-Algorithmen. „Greedy“ heißt gierig: Sie bevorzugen in jedem Schritt die momentan aussichtsreichste Teillösung. Anders als manche andere Greedy-Algorithmen berechnet Dijkstra unter der Voraussetzung positiver Kantengewichte eine optimale, also kürzeste Lösung.

Zu jedem Knoten merkst du dir zwei Werte: die Distanz (die bisher kürzeste bekannte Strecke vom Start) und den Vorgänger (den Knoten davor auf diesem Weg).

Anfang: Der Startknoten hat die Distanz 0. Alle anderen Knoten haben die Distanz ∞ (unendlich), ihr Vorgänger ist unbekannt.

Dann wiederholst du, solange es unbesuchte Knoten gibt: Wähle unter den unbesuchten Knoten den mit der kleinsten Distanz und markiere ihn als besucht. Für jeden unbesuchten Nachbarn rechnest du die Gesamtdistanz: Kantengewicht plus die Distanz des gewählten Knotens. Ist dieser Wert kleiner als die gespeicherte Distanz, übernimmst du ihn, und der gewählte Knoten wird Vorgänger des Nachbarn.

Die Distanz eines besuchten Knotens bleibt gespeichert. Die Distanzen noch nicht abgearbeiteter Knoten können sich dagegen noch verringern.

Beim Ausführen hast du für jeden Knoten einen Vorgänger gespeichert. Den kürzesten Weg zu einem Zielknoten findest du, indem du am Zielknoten beginnst und immer zum Vorgänger springst. Das wiederholst du, solange ein Vorgänger existiert. Der Vorgänger des Startknotens ist null, also nicht vorhanden. Dort hörst du auf.

Jeden gefundenen Knoten schreibst du vorn in die Wegliste. So steht der Weg am Ende vom Start zum Ziel. Die Länge des Wegs ist die Endwert-Distanz des Zielknotens.

Dijkstra ändert eine einmal festgelegte Distanz zum Startknoten nicht mehr. Das ist bei positiven Kantengewichten in Ordnung: Ein später gefundener kürzerer Weg hätte eine kürzere Teilstrecke gehabt, die man früher hätte untersuchen müssen.

Bei negativen Kantengewichten stimmt das nicht mehr. Dann kann jede Teilstrecke für sich eine kürzeste Strecke sein, und trotzdem lässt sich die Gesamtdistanz über einen längeren Teilweg verbessern, wenn eine negative Kante die Weglänge wieder reduziert. Dijkstra hat die Distanz aber schon festgelegt und ändert sie nicht mehr.

Deshalb können negative Kantengewichte zu nicht-optimalen Lösungen führen. Wie das Verfahren im Einzelnen versagt, betrachten wir hier nicht. Für Graphen mit negativen Kantengewichten gibt es den Bellman-Ford-Algorithmus als Alternative.

Die Breitensuche durchsucht einen Graphen ausgehend vom Startknoten Level für Level: Zuerst werden alle Knoten bearbeitet, die direkt erreichbar sind, dann die nächste Ebene. Jede durch Breitensuche gefundene Lösung hat den kürzesten Abstand zum Wurzelknoten. Mit Kantengewichten muss das Ergebnis, das am nächsten zum Startknoten liegt, aber nicht notwendigerweise auch das mit den geringsten Pfadkosten sein. Nur wenn alle Kantengewichte gleich sind, ist jede durch Breitensuche gefundene Lösung optimal. Dijkstra rechnet dagegen mit den Gewichten.

Ein Spannbaum ist ein Teilgraph eines ungerichteten Graphen, der ein Baum ist und alle Knoten des Graphen enthält. Das Gewicht eines Graphen ist die Summe seiner Kantengewichte. Ein Spannbaum heißt minimal, wenn kein anderer Spannbaum im selben Graphen ein geringeres Gewicht hat. Einen minimalen Spannbaum berechnest du zum Beispiel mit dem Algorithmus von Kruskal: Du gehst die Kanten nach aufsteigendem Gewicht durch und nimmst jede Kante auf, die mit den bisher gewählten Kanten keinen Kreis bildet.

Die Vorgänger von Dijkstra bilden ebenfalls einen Baum aus kürzesten Pfaden vom Start. Dieser Baum ist aber nicht notwendigerweise minimal. Dijkstra fragt also: „Wie komme ich vom Start am kürzesten zu jedem Knoten?“ Ein minimaler Spannbaum fragt: „Wie verbinde ich alle Knoten mit dem kleinsten Gesamtgewicht?“