Dijkstra-Algorithmus

Animation des Dijkstra-Algorithmus

Der Algorithmus von Dijkstra (nach seinem Erfinder Edsger W. Dijkstra) ist ein Algorithmus aus der Klasse der Greedy-Algorithmen und löst das Problem der kürzesten Pfade für einen gegebenen Startknoten. Er berechnet somit einen kürzesten Pfad zwischen dem gegebenen Startknoten und einem (oder allen) der übrigen Knoten in einem kantengewichteten Graphen. Die Kantengewichte des Graphen dürfen dabei nicht negativ sein. Für Graphen mit negativen Gewichten ist der Bellman-Ford-Algorithmus geeignet.

Für unzusammenhängende ungerichtete Graphen ist der Abstand zu denjenigen Knoten unendlich, zu denen kein Pfad vom Startknoten aus existiert. Dasselbe gilt auch für gerichtete nicht stark zusammenhängende Graphen.

Algorithmus

Informeller Algorithmus

Die Grundidee des Algorithmus ist es, immer derjenigen Kante zu folgen, die den kürzesten Streckenabschnitt vom Startknoten aus verspricht. Andere Kanten werden erst dann verfolgt, wenn alle kürzeren Streckenabschnitte beachtet wurden. Dieses Vorgehen gewährleistet, dass bei Erreichen eines Knotens kein kürzerer Pfad zu ihm existieren kann. Eine einmal berechnete Distanz zwischen dem Startknoten und einem erreichten Knoten wird nicht mehr geändert. Dieses Vorgehen wird fortgesetzt, bis die Distanz des Zielknotens berechnet wurde (single-pair shortest path) oder die Distanzen aller Knoten zum Startknoten bekannt sind (single-source shortest path).

Berechnung der kürzesten Wege zum linken Knoten

Der Algorithmus lässt sich durch die folgenden Schritte beschreiben. Es werden sowohl die kürzesten Wegstrecken als auch deren Knotenfolgen berechnet.

1. Weise allen Knoten die beiden Eigenschaften "Distanz" und "Vorgänger" zu. Initialisiere die Distanz im Startknoten mit 0 und in allen anderen Knoten mit ∞.
2. Solange es noch unbesuchte Knoten gibt, wähle darunter denjenigen mit minimaler Distanz aus und
   1. Speichere, dass dieser Knoten schon besucht wurde
   2. Berechne für alle noch unbesuchten Nachbarknoten die Summe des jeweiligen Kantengewichtes und der Distanz im aktuellen Knoten
   3. Ist dieser Wert für einen Knoten kleiner als die dort gespeicherte Distanz, aktualisiere sie und setze den aktuellen Knoten als Vorgänger

      Dieser Schritt wird auch als Update oder Relaxieren bezeichnet.

In dieser Form berechnet der Algorithmus ausgehend von einem Startknoten die kürzesten Wege zu allen anderen Knoten. Ist man dagegen nur an dem Weg zu einem ganz bestimmten Knoten interessiert, so kann man in Schritt (2) schon abbrechen, wenn der gesuchte Knoten der aktive ist.

Negative Kantengewichte können zu nicht-optimalen Lösungen führen

Aufgrund der Eigenschaft, einmal festgelegte Distanzen zum Startknoten nicht mehr zu verändern, gehört der Dijkstra-Algorithmus zu den Greedy-Algorithmen, die in jedem Schritt die momentan aussichtsreichste Teillösung bevorzugen. Anders als manche andere Greedy-Algorithmen berechnet der Dijkstra-Algorithmus jedoch stets die optimale Lösung. Diese Eigenschaft basiert auf der Annahme, dass die kürzesten Teilstrecken zwischen Knoten in einem Pfad zusammen die kürzeste Strecke auf diesem Pfad bilden. Unter der Voraussetzung positiver Kantengewichte ist die Annahme gültig, denn fände man nachträglich einen kürzeren Weg vom Startknoten zu einem Zielknoten, hätte man auch dessen kürzere Teilstrecke früher untersuchen müssen, um den Algorithmus korrekt durchzuführen. Dann hätte man aber über die kürzere Teilstrecke den Zielknoten früher gefunden als auf dem längeren Weg.

Die Annahme trifft jedoch nicht mehr zu, wenn der Graph negative Kantengewichte enthält. Dann kann jede Teilstrecke für sich zwar eine kürzeste Strecke zwischen den Endpunkten sein, man könnte jedoch über einen längeren Teilweg die Gesamtdistanz verbessern, wenn eine negative Kante die Weglänge wieder reduziert. Im Bild mit den Knoten 1, 2, 3 und 4 würde der Dijkstra-Algorithmus den kürzesten Weg von 1 nach 3 über 2 finden, da der Schritt zu 4 insgesamt schon länger ist als der gesamte obere Pfad. Die negative Kante bewirkt aber, dass der untere Pfad kürzer ist.

Algorithmus in Pseudocode

Die folgenden Zeilen Pseudocode beschreiben eine Funktion namens Dijkstra, die einen Graphen und einen Startknoten im Graphen als Eingabe erhält. Der Startknoten gibt den Knoten an, von dem aus die kürzesten Wege zu allen Knoten gesucht werden. Das Ergebnis ist eine Liste, die zu jedem Knoten v den Vorgängerknoten auf dem Weg vom Startknoten zu v angibt.

Der Graph besteht aus Knoten und gewichteten Kanten zwischen seinen Knoten. Existiert eine Kante zwischen zwei Knoten, so sind sie jeweils Nachbarn. Das Kantengewicht zwischen benachbarten Knoten u und v wird im Pseudocode als abstand_zwischen(u,v) angegeben.

Zunächst werden abhängig vom Graphen und Startknoten die Abstände und Vorgänger initialisiert. Dies geschieht in der Methode initialisiere. Der eigentliche Algorithmus verwendet eine Methode distanz_update, die ein Update der Abstände durchführt, falls ein kürzerer Weg gefunden wurde.

 1  Funktion Dijkstra(Graph, Startknoten):
 2      initialisiere(Graph,Startknoten,abstand[],vorgänger[],Q)
 3      solange Q nicht leer:                       // Der eigentliche Algorithmus
 4          u := Knoten in Q mit kleinstem Wert in abstand[]
 5          entferne u aus Q                                // für u ist der kürzeste Weg nun bestimmt
 6          für jeden Nachbarn v von u:
 7              falls v in Q:
 8                 distanz_update(u,v,abstand[],vorgänger[])   // prüfe Abstand vom Startknoten zu v
 9      return vorgänger[]

Die Initialisierung setzt die Abstände auf unendlich und die Vorgänger als unbekannt. Nur der Startknoten hat die Distanz 0. Die Menge Q enthält die Knoten, zu denen noch kein kürzester Weg gefunden wurde.

 1  Methode initialisiere(Graph,Startknoten,abstand[],vorgänger[],Q):
 2      für jeden Knoten v in Graph:
 3          abstand[v] := unendlich
 4          vorgänger[v] := null
 5      abstand[Startknoten] := 0
 6      Q := Die Menge aller Knoten in Graph

Der Abstand vom Startknoten zum Knoten v verkürzt sich dann, wenn der Weg zu v über u kürzer als der bisher bekannte Weg ist. Entsprechend wird u zum Vorgänger von v auf dem kürzesten Weg.

 1  Methode distanz_update(u,v,abstand[],vorgänger[]):
 2      alternativ := abstand[u] + abstand_zwischen(u, v)   // Weglänge vom Startknoten nach v über u
 3      falls alternativ < abstand[v]:
 4          abstand[v] := alternativ
 5          vorgänger[v] := u

Falls man nur am kürzesten Weg zwischen zwei Knoten interessiert ist, kann man den Algorithmus nach Zeile 5 der Dijkstra-Funktion abbrechen lassen, falls u = Zielknoten ist.

Den kürzesten Weg zu einem Zielknoten kann man nun durch Iteration über die vorgänger ermitteln:

1  Funktion erstelleKürzestenPfad(Zielknoten,vorgänger[])
2   Weg[] := [Zielknoten]
3   u := Zielknoten
4   solange vorgänger[u] nicht null:   // Der Vorgänger des Startknotens ist null
5       u := vorgänger[u]
6       füge u am Anfang von Weg[] ein
7   return Weg[]

Implementierung

Siehe auch: Repräsentation von Graphen im Computer

Knoten und Kanten zwischen Knoten lassen sich meistens durch Matrizen oder Zeigerstrukturen darstellen. Auch auf den Vorgänger eines Knotens kann ein Zeiger verweisen. Die Abstände der Knoten können in Feldern gespeichert werden.

Für eine effiziente Implementierung wird die Menge Q der Knoten, für die noch kein kürzester Weg gefunden wurde, durch eine Prioritätswarteschlange implementiert. Die aufwändige Initialisierung findet nur einmal statt, dafür sind die wiederholten Zugriffe auf Q effizienter. Als Schlüsselwert für den Knoten wird sein jeweiliger Abstand verwendet, der im Pseudocode mit abstand[v] angegeben ist. Verkürzt sich der Abstand, ist eine teilweise Neusortierung der Warteschlange nötig.

Beispiel

Ein Beispiel für die Anwendung des Algorithmus von Dijkstra ist die Suche nach einem kürzesten Pfad auf einer Landkarte. Im hier verwendeten Beispiel will man in der unten gezeigten Landkarte von Deutschland einen kürzesten Pfad von Frankfurt nach München finden.

Die Zahlen auf den Verbindungen zwischen zwei Städten geben jeweils die Entfernung zwischen den beiden durch die Kante verbundenen Städten an. Die Zahlen hinter den Städtenamen geben die ermittelte Distanz der Stadt zum Startknoten Frankfurt an, oo steht dabei für ∞, also für unbekannte Distanz. Die hellgrau unterlegten Knoten sind die Knoten, deren Abstand relaxiert wird (also verkürzt wird, falls eine kürzere Strecke gefunden wurde), die dunkelgrau unterlegten Knoten sind diejenigen, zu denen der kürzeste Weg von Frankfurt bereits bekannt ist.

Die Auswahl des nächsten Nachbarn erfolgt nach dem Prinzip einer Prioritätswarteschlange. Relaxierte Abstände erfordern daher eine Neusortierung.

• Beispiel
• 

  Ausgangssituation: Nicht-initialisierter Graph mit Startknoten Frankfurt und Zielknoten München

• 

  Entfernungen vom Startknoten (Frankfurt) ermitteln (relax), Neusortieren der Prioritätswarteschlange Q (1. Mannheim, 2. Kassel, 3. Würzburg, ...)

• 

  Mannheim ist der nächstliegende Knoten, relax mit Nachbarknoten Karlsruhe, nächster Vorgänger von Karlsruhe ist nun Mannheim, Neusortieren von Q (1. Karlsruhe, 2. Kassel, 3. Würzburg, ...)

• 

  Dem Startpunkt nächstliegender zu untersuchender Knoten laut Q ist nun Karlsruhe, relax mit Augsburg, Neusortieren von Q (1. Kassel, 2. Würzburg, 3. Augsburg, ...)

• 

  Nächstliegender zu untersuchender Knoten ist nun Kassel, relax mit München, Neusortieren von Q (1. Würzburg, 2. Augsburg, 3. München, ...)

• 

  Nächstliegender zu untersuchender Knoten ist nun Würzburg, relax mit Erfurt und Nürnberg, Neusortieren von Q (1. Nürnberg, 2. Erfurt, 3. Augsburg, 4. München, ...)

• 

  Nächstliegender zu untersuchender Knoten ist nun Nürnberg, relax mit München und Stuttgart, Neusortieren von Q (1. Erfurt, 2. Augsburg, 3. München, 4. Stuttgart, ...)

• 

  Nächstliegender zu untersuchender Knoten ist nun Erfurt, relax mit niemandem, Neusortieren von Q (1. Augsburg, 2. München, 3. Stuttgart, ...)

• 

  Nächstliegender zu untersuchender Knoten ist nun Augsburg, relax mit München, Neusortieren von Q (1. München, 2.Stuttgart)

• 

  Zielknoten soll untersucht werden: Kürzester Weg nach München ist nun bekannt; Rekonstruktion mittels erstelleKürzestenPfad(). Dieser ist: Frankfurt-Würzburg-Nürnberg-München.

Grundlegende Konzepte und Verwandtschaften

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

Nach Ende des Algorithmus ist in den Vorgängerzeigern π ein Spannbaum der Komponente von $\left. s \right.$ aus kürzesten Pfaden von $\left. s \right.$ zu allen Knoten der Komponente verzeichnet. Dieser Baum ist jedoch nicht notwendigerweise auch minimal, wie die Abbildung zeigt:

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

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

Zeitkomplexität

Im Folgenden sei m die Anzahl der Kanten und n die Anzahl der Knoten.

Die Zeitkomplexität des Algorithmus hängt in hohem Maße von der Datenstruktur ab, welche zur Speicherung der noch nicht besuchten Knoten (Q) benutzt wird. Im Normalfall wird man hier auf eine Vorrangwarteschlange zurückgreifen, indem man dort die Knoten als Elemente mit ihrer jeweiligen bisherigen Distanz als Schlüssel/Priorität verwendet.

Betrachtet man den Algorithmus unter diesem Aspekt ergibt sich folgender Aufwand:

Das „Füllen“ von Q in Zeile 02 wird dadurch erreicht, dass man jeden Knoten sowie seine Priorität (= Distanz) mittels insert in die Warteschlange einfügt; das wird, da es insgesamt n Knoten gibt, n Mal durchgeführt.

Da in Zeile 04 jeweils ein Knoten aus Q (bzw. der Warteschlange) entfernt wird, folgt, dass die Schleife in Zeile 03 ebenfalls n Mal durchlaufen wird (ein evtl. früherer Abbruch wegen Erreichen von g sei hier ausgenommen). In jedem Schleifendurchlauf muss geprüft werden, ob die Warteschlange leer ist (empty, Zeile 03) und es muss das nächste Element mit der niedrigsten Priorität entfernt werden (extractMin, Zeile 04); die beiden Operationen werden also jeweils n Mal durchgeführt.

Die Anzahl Aufrufe der relax-Funktion kann zwar für jeden Durchlauf der Schleife in Zeile 07 variieren (da die Anzahl der von jedem Knoten u ausgehenden Kanten natürlich unterschiedlich sein kann), insgesamt über die Laufzeit des gesamten Algorithmus gesehen wird die Schleife aber m Mal ausgeführt, da jeder Knoten nur einmal betrachtet wird, und somit jede von ihm ausgehende Kante ebenfalls nur einmal betrachtet werden kann. Es werden somit alle ausgehenden Kanten aller Knoten im Graphen überprüft und damit erhält man natürlich alle Kanten des Graphen, also m Stück).

Sollte sich hier die bisher berechnete Distanz des Knotens v verringern, muss natürlich auch die Priorität in der Warteschlange mittels decreaseKey entsprechend verringert werden. Das passiert im Worst Case (im – unwahrscheinlichen – Fall dass die Überprüfung jeder Kante einen kürzeren Weg liefert) höchstens m Mal.

Der Vollständigkeit halber sollte man außerdem auch noch das Setzen von d[v] und π[v] in der relax Funktion betrachten, jedoch lässt sich dies jeweils in konstanter Zeit mit der Komplexität realisieren.

Insgesamt ergibt sich also eine Komplexität von $\mathcal{O} \left( n\cdot(1 + T_\mathrm{insert}+T_\mathrm{empty}+T_\mathrm{extractMin}) + m\cdot (1 + T_\mathrm{decreaseKey}) \right)$.

Würde man zur Verwaltung der Knoten nun z. B. einfach eine Liste verwenden, ergäbe das eine Laufzeit von $\mathcal{O}(n^2 + m)$; insert, empty und decreaseKey lassen sich alle in $\mathcal{O}(1)$ realisieren, das Suchen des Elements mit der kleinsten Priorität erfordert eine lineare Suche mit $\mathcal{O}(n)$.

Besser fährt man hier mit der Verwendung der Datenstruktur Fibonacci-Heap. Diese ermöglicht es ebenfalls, die Operationen insert, empty und decreaseKey (amortisiert betrachtet) in $\mathcal{O}(1)$ zu realisieren, die Komplexität von extractMin ist hier $\mathcal{O}(\log n)$. Die gesamte Laufzeit beträgt dann lediglich $\mathcal{O}(n\cdot\log n + m)$.

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.

Einige topologische Indizes, etwa der J-Index von Balaban, benötigen gewichtete Distanzen zwischen den Atomen eines Moleküls. Die Gewichtung ist in diesen Fällen die Bindungsordnung.

Dijkstras Algorithmus wird auch im Internet als Routing-Algorithmus im OSPF- und OLSR-Protokoll eingesetzt. Das letztere Optimized Link State Routing-Protokoll ist eine an die Anforderungen eines mobilen drahtlosen LANs angepasste Version des Link State Routing. Es ist wichtig für mobile Ad-hoc-Netze. Eine mögliche Anwendung davon sind die Freien Funknetze.

Andere Verfahren zur Berechnung kürzester Pfade

Weiß man genug über die einzelnen Kantengewichte des Graphen, um daraus eine Heuristik für die Kosten der einzelnen Knoten ableiten zu können, ist es möglich den Algorithmus von Dijkstra mittels dieser Heuristik zum A*-Algorithmus zu erweitern. Um alle kürzesten Pfade von einem Knoten zu allen anderen Knoten in einem Graphen zu berechnen, kann man den Bellman-Ford-Algorithmus verwenden, welcher auch mit negativen Kantengewichten umgehen kann. Der Algorithmus von Floyd und Warshall berechnet schlussendlich nicht nur die kürzesten Pfade eines Knotens zu allen anderen Knoten im Graph, sondern die kürzesten Pfade aller Knoten zueinander.

Literatur

• Thomas H Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Algorithmen – eine Einführung. Oldenbourg, München, Wien 2004, ISBN 3-486-27515-1, S. 598–604. 
• Edsger W. Dijkstra: A note on two problems in connexion with graphs. In: Numerische Mathematik. 1 (1959), S. 269–271

Algorithmen zum Auffinden minimaler Spannbäume

• Algorithmus von Kruskal
• Algorithmus von Borůvka
• Algorithmus von Prim

Weblinks

•  Wikibooks: Dijkstra-Algorithmus – Implementierungen in der Algorithmensammlung
• Java-Applet zu Dijkstra und anderen (englisch)
• Interaktive Visualisierung und Animation von Dijkstras Algorithmus, geeignet für Personen ohne Vorkenntnisse von Algorithmen (englisch)
• Implementierung in C (englisch)
• Erklärung anhand eines analogen Modells (PDF-Datei; 213 kB) und weitere Informationen
• Öffentliche Softwarebibliothek in Java mit diesem und anderen Algorithmen (englisch)
• Java Implementierung – Simulation / Auswertung (englisch)