Dijkstra-Algorithmus

Der Algorithmus von Dijkstra (nach seinem Erfinder Edsger W. Dijkstra) dient der Berechnung eines kürzesten Pfades zwischen einem Startknoten und einem beliebigen Knoten in einem kantengewichteten Graphen. Die Gewichte dürfen dabei nicht negativ sein.

Für nicht zusammenhängende, ungerichtete Graphen kann der Abstand zu bestimmten Knoten auch unendlich sein, wenn ein Pfad zwischen Startknoten und diesen Knoten nicht existiert. Dasselbe gilt auch für gerichtete, nicht stark zusammenhängende Graphen.

Algorithmus

G bezeichnet den gewichteten Graphen mit V als Knotenmenge, E als Kantenmenge und Kosten als Gewichtsfunktion. s ist der Startknoten, U ist die Menge der noch zu bearbeitenden Knoten und z ist ggf. ein spezieller Zielknoten, bei dem abgebrochen werden kann, wenn seine Distanz zum Startknoten bekannt ist.

Nach Ende des Algorithmus enthält Distanz die Abstände aller Knoten zu s. In Vorgänger ist ein spannender Baum der von s aus ausgehenden minimalen Wege in Form eines In-Tree gespeichert.

Wird bei Erreichen von z abgebrochen (mit #optional gekennzeichet), so enthalten Distanz und Vorgänger diese Werte nur für alle zuvor betrachteten Knoten. Dies sind mindestens die, die kleineren Abstand als z zu s besitzen.

01  für jedes v aus V
02      Distanz(v) := unendlich, Vorgänger(v) := kein
03  Distanz(s) := 0, Vorgänger(s) := s, U := V
04
05  solange U nicht leer
06      wähle u aus U mit Distanz(u) minimal                               
07      U := U - {u}                                                     
08      wenn u = z dann STOP   # optional
09      für jedes (u,v) aus E mit v aus U
10          wenn Distanz(u) + Kosten(u,v) < Distanz(v) dann
11              Distanz(v) := Distanz(u) + Kosten(u,v)
12              Vorgänger(v) := u

Grundlegende Konzepte und Verwandschaften

Der Algorithmus ist ein Greedy-Algorithmus, der sukzessive den nächstbesten Knoten, der einen kürzesten Pfad besitzt (Zeile 06), in eine Ergebnismenge aufnimmt, bzw. diesen aus der Menge der noch zu bearbeitenden Knoten entfernt (Zeile 07). Damit findet sich eine Verwandschaft zur Breitensuche, die ebenfalls solch ein gieriges Verhalten aufweist.

Ein alternativer Algorithmus zur Suche kürzester Pfade, der sich dagegen auf das Optimalitätsprinzip von Bellman stützt, ist der Floyd-Warshall-Algorithmus. Das Optimalitätsprinzip besagt, dass wenn der kürzeste Pfad von A nach C über B führt, der Teilpfad A B auch der kürzeste Pfad von A nach B sein muss.

Ein weiterer alternativer Algorithmus ist der A*-Algorithmus der den Algorithmus von Dijkstra um eine Abschätzfunktion erweitert. Falls diese gewisse Eigenschaften erfüllt, kann damit der kürzeste Pfad unter Umständen schneller gefunden werden.

Berechnung eines Spannbaumes

Beschreibung

Nach Ende des Algorithmus ist in Vorgänger ein spannender Baum der Komponente von s aus kürzesten Pfaden von s zu allen Knoten der Komponente verzeichnet. Dieser Baum ist jedoch nicht notwendigerweise auch minimal, wie die Abbildung zeigt:

Sei x eine Zahl größer 0. Minimal spannende Bäume sind entweder durch die Kanten {a,s} und {a,b} oder {b,s} und {a,b) gegeben. Die Gesamtkosten eines minimal spannenden Baumes betragen 2+x. Dijkstras Algorithmus liefert mit Startpunkt s die Kanten {a,s} und {b,s} als Ergebnis. Die Gesamtkosten dieses spannenden Baumes betragen 2+2x.

Die Berechnung eines minimalen Spannbaumes ist mit dem Algorithmus von Prim möglich.

Zeitkomplexität

Im folgenden sei m die Anzahl der Kanten und n die Anzahl der Knoten. Der Algorithmus von Dijkstra muss n mal den nächsten minimalen Knoten u bestimmen (Zeilen 05 und 06). Eine Möglichkeit wäre jedes mal diesen mittels Durchlaufen durch eine Knotenliste zu bestimmen. Die Laufzeit beträgt dann $O(n^{2})$ . Eine effizientere Möglichkeit zur Liste bietet die Verwendung der Datenstruktur Fibonacci-Heap. Die Laufzeit beträgt dann lediglich $O(m+n\cdot \log(n))$ .

Anwendungen

Routenplaner sind ein prominentes Beispiel, bei dem dieser Algorithmus eingesetzt werden kann. Der Graph repräsentiert hier das Straßennetz, welches verschiedene Punkte miteinander verbindet. Gesucht ist die kürzeste Route zwischen zwei Punkten.

Dijkstras Algorithmus wird auch im Internet als Routing-Algorithmus in OSPF eingesetzt.

Siehe auch

Literatur

E. W. Dijkstra: A note on two problems in connexion with graphs. In: Numerische Mathematik. 1 (1959), S. 269–271

Weblinks

Ein anschauliches Beispiel