Dijkstra-Algorithmus

Zweck und Voraussetzungen

Der Dijkstra-Algorithmus ist ein Greedy-Algorithmus zur Berechnung kürzester Pfade in einem kantengewichteten Graphen. Ausgehend von einem Startknoten bestimmt er einen kürzesten Pfad zu einem bestimmten Zielknoten oder zu allen übrigen Knoten. Kantengewichte können dabei Entfernungen, Kosten oder Gewichte bedeuten.

Voraussetzung ist, dass der Graph keine negativen Kantengewichte enthält. In einem unzusammenhängenden ungerichteten Graphen ist der Abstand zu nicht erreichbaren Knoten unendlich; Entsprechendes gilt für gerichtete Graphen, die nicht stark zusammenhängend sind. Die Greedy-Idee besteht darin, immer den noch nicht besuchten Knoten mit der momentan kleinsten bekannten Distanz zu wählen. Sobald ein Knoten ausgewählt wurde, ist seine Distanz endgültig und kann nicht mehr verbessert werden.

Ablauf und Relaxierung

Jeder Knoten erhält zwei Attribute: Distanz und Vorgänger. Zu Beginn hat der Startknoten die Distanz 0, alle anderen Knoten die Distanz ∞. Solange unbesuchte Knoten vorhanden sind, wird der Knoten mit der kleinsten bisher bekannten aufsummierten Distanz ausgewählt und als besucht markiert.

Danach werden seine noch unbesuchten Nachbarn geprüft. Für einen Nachbarn wird die alternative Distanz aus der Distanz zum aktuellen Knoten plus dem Gewicht der verbindenden Kante berechnet. Ist sie kleiner als die bisher gespeicherte Distanz, werden Distanz und Vorgänger aktualisiert. Dieses Aktualisieren heißt Update oder Relaxation/Relaxierung.

Die Vorgänger speichern die Knotenfolge eines kürzesten Weges. Soll nur ein Weg zwischen Start- und Zielknoten gefunden werden, darf der Algorithmus enden, sobald der Zielknoten als aktueller Knoten ausgewählt wird. Negative Kantengewichte können dagegen zu nicht optimalen Lösungen führen, weil ein bereits endgültig behandelter Knoten später über eine negative Kante doch noch günstiger erreichbar sein könnte.

Pseudocode und Wegrekonstruktion

Im Pseudocode heißt der aktuelle Betrachtungsknoten u, ein zu prüfender Nachbar v. Die Menge Q enthält alle Knoten, für die noch kein kürzester Weg bestimmt wurde. Der Hauptschritt lautet: Wähle u in Q mit dem kleinsten Wert abstand[u], entferne u aus Q und führe für jeden noch in Q befindlichen Nachbarn v ein distanz_update aus.

Dabei gilt: alternativ := abstand[u] + abstand_zwischen(u,v). Falls alternativ < abstand[v], werden abstand[v] := alternativ und vorgänger[v] := u gesetzt. Nach dem Ende liefert vorgänger[] für jeden Knoten seinen Vorgänger auf dem Weg vom Startknoten.

Ein konkreter Weg wird vom Zielknoten aus rekonstruiert: Man folgt wiederholt den Vorgängern bis zum Startknoten, dessen Vorgänger null ist, und fügt die dabei gefundenen Knoten jeweils am Anfang der Wegliste ein.

Datenstrukturen und Laufzeit

Knoten und Kanten können durch Matrizen oder Zeigerstrukturen dargestellt werden; Abstände lassen sich in Feldern speichern. Für Q ist eine Prioritätswarteschlange zweckmäßig: Ihr Schlüssel ist die bisherige Distanz eines Knotens. Wird eine Distanz durch Relaxierung kleiner, muss die Warteschlange teilweise neu sortiert werden. Als Darstellungen werden unter anderem Entfernungstabellen, Adjazenzmatrizen und Adjazenzlisten verwendet.

Für Graphen ohne negative Kantengewichte hängt die Laufzeit von der Kantenzahl |E|, der Knotenzahl |V| und der Datenstruktur für Q ab: O(|E|·T_dk + |V|·T_em). T_dk bezeichnet die Kosten von decrease-key, T_em die von extract-minimum. Mit Liste oder Array ergibt sich O(|E|+|V|²)=O(|V|²). Mit einem Fibonacci-Heap beträgt die optimale Laufzeit für G=(V,E) O(|V|log(|V|)+|E|).

Beispiel, Spannbaum und verwandte Verfahren

Im Kartenbeispiel wird von Frankfurt nach München gesucht. Nach der Initialisierung werden die Knoten gemäß ihrer Priorität untersucht und ihre Distanzen relaxiert. Die Reihenfolge beginnt mit Mannheim, dann Karlsruhe, Kassel, Würzburg, Nürnberg, Erfurt und Augsburg. Sobald München untersucht werden soll, ist der kürzeste Weg bekannt: Frankfurt–Würzburg–Nürnberg–München.

Die Vorgängerzeiger bilden nach dem Algorithmus einen Teil-Spannbaum der vom Startknoten s erreichbaren Komponente mit kürzesten Wegen von s. Dieser ist aber nicht unbedingt ein minimaler Spannbaum. Für x > 0 kosten minimale Spannbäume mit {a,s} und {a,b} oder mit {b,s} und {a,b} insgesamt 2+x. Dijkstra mit Start s kann hingegen {a,s} und {b,s} liefern; dieser Spannbaum kostet 2+2x. Minimale Spannbäume lassen sich mit Prim oder Kruskal berechnen.

Alternativen sind Floyd-Warshall, der auf dem Optimalitätsprinzip von Bellman beruht und alle kürzesten Pfade zwischen allen Knoten berechnet, sowie A*, das Dijkstra um eine Abschätzfunktion erweitert und unter passenden Eigenschaften schneller sein kann. Bellman-Ford berechnet alle kürzesten Wege von einem Knoten und kann negative Kantengewichte behandeln.

Forschung und Anwendungen

Für reell gewichtete gerichtete Graphen mit nichtnegativen Gewichten beschrieben Duan u. a. (2025) einen deterministischen Algorithmus mit O(m log^(2/3)n) im Comparison-Addition-Modell. Er benötigt nur Distanzen statt der vollständigen Reihenfolge der Knoten nach Distanz, verkleinert die relevante „Frontier“ rekursiv und verbindet Dijkstra-artige Extraktionen mit Bellman-Ford-artigen Mehrschritt-Relaxationen. Damit wird die klassische Sortierbarriere O(m+n log n) für SSSP umgangen. Müssen vollständige Distanzordnungen ausgegeben werden, bleibt eine universelle Optimalität bestehen. Für ungerichtete Graphen gab es bereits Verbesserungen, etwa Pettie und Ramachandran (2005) mit O(mα(m,n)+min{n log n, n log log r}).

Anwendungen sind Routenplaner, bei denen ein Verkehrsnetz als Graph dargestellt wird, sowie topologische Indizes wie der J-Index von Balaban: Dort entsprechen gewichtete Distanzen zwischen Atomen den Bindungsordnungen. Im Internet dient der Algorithmus als Routing-Algorithmus in OSPF, IS-IS und OLSR. OLSR ist für mobile drahtlose LANs und mobile Ad-hoc-Netze angepasst und kann in freien Funknetzen eingesetzt werden. Auch das Münzproblem kann mit dem Dijkstra-Algorithmus gelöst werden.