G bezeichnet den gewichteten Graphen mit V (engl. vertex) als Knotenmenge, E (engl. edge) als Kantenmenge und w als Gewichtsfunktion, welche Kanten auf positive reelle Zahlen abbildet. Der Knoten s ist der Startknoten, Q ist die Prioritätswarteschlange der noch zu bearbeitenden Knoten und g ist ggf. ein spezieller Zielknoten, bei dem abgebrochen werden kann, wenn seine Distanz zum Startknoten bekannt ist.
Wird bei Erreichen von g abgebrochen, so enthalten dund π[v diese Werte nur für alle zuvor betrachteten Knoten v. Das sind mindestens die, die kleineren Abstand als g zu s besitzen.
/*
* Algorithmus zur Rekonstruktion des kürzesten Pfades
*
---
* p: berechneter kürzester Pfad
* n: Zielknoten
*/
reconstruct_shortest_path (n, p)
{
// Prüfe ob schon wieder beim Startknoten angekommenwhile (π(n) != NIL))
{
push(n, p); // Füge Knoten dem Pfad hinzu
n := π(n); // Mache dasselbe für den Vorgängerknoten
}
return p; // Liefere den gefundenen Pfad zurück
}
/*
* Algorithmus zum Initialisieren des Graphen
*
--
* G: Zu untersuchender Graph
* s: Startknoten
*/
initialize(G, s)
{
// Setze die Entfernung zu allen Knoten auf unendlich
forall v do
d* := ∞
d* := 0;
}
/*
* Algorithmus zum Relaxieren einer Kante
*
--
* u: Knoten, der gerade expandiert wurde
* v: Aktuell betrachteter Nachfolger von u
* w: Gewichtsfunktion zum Berechnen der Kosten für eine Kante
* d: Funktion zum Berechnen des Abstandes eines Knotens zum Startknoten
*/
relax(u,v,w)
{
// Prüfe, ob der Weg über u zu v kürzer ist als der aktuelleif d> d[u + w(u,v) {
// Neuer Weg kürzer als bisher gefundener Weg
// Aktualisiere geschätzte restliche Weglänge
d:= d[u + w(u,v);
// Aktualisiere Vorgänger in kürzestem Pfad
π* := u;
}
else
; // ''Ändere nichts, da bereits besserer Pfad bekannt
}
/*
* Der eigentliche Algorithmus von Dijkstra
*
-
* G: Zu untersuchender Graph
* s: Startknoten
* g: Der Zielknoten
* w: Gewichtsfunktion zum Berechnen der Kosten für eine Kante
* d: Funktion zum Berechnen des Abstandes eines Knotens zum Startknoten
* Q: Prioritätswarteschlange der Knoten, aufsteigend nach d-Werten sortiert
*/
Dijkstra (s, g, w, h, G) {
01 initialize(G, s);
02 Q := V*; // Füge alle Knoten aus dem Graph in die Warteschlage ein
03 whilenot isEmpty(Q) {
04 // Betrachte Knoten mit geringsten Abstand zum Startknoten
05 u := pop(Q);
06 if (u == g) then
07 return reconstructShortestPath(g);
08 else {
09 // Betrachte alle vom aktuellen Knoten u aus erreichbaren Knoten (Nachfolger)
10 forall v := sucessors(u) do {
11 // relaxiere die Kante zwischen u und seinem Nachfolger
12 relax(u, v, w);
13 }
14 }
15 }
15 // Es konnte kein Pfad gefunden werden
16 return fail;
17 }
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 rechts 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.
Der Algorithmus gehört zur Klasse der Greedy-Algorithmen. Sukzessive wird der nächstbeste Knoten, der einen kürzesten Pfad besitzt (Zeile 04), aus der Menge der noch zu bearbeitenden Knoten entfernt. Damit findet sich eine Verwandtschaft 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.
Nach Ende des Algorithmus ist in den Vorgängerzeigern π 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 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 . Dijkstras Algorithmus liefert mit Startpunkt s die Kanten {a,s} und {b,s} als Ergebnis. Die Gesamtkosten dieses spannenden Baumes betragen .
Im Folgenden sei die Anzahl der Kanten und 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 insg. Knoten gibt, also 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 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 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), insg. über die Laufzeit des gesamten Algorithmus gesehen wird die Schleife aber 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 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 Mal.
Der Vollständigkeit halber sollte man außerdem auch noch das Setzen von dund π[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 .
Würde man zur Verwaltung der Knoten nun z.B. einfach eine Liste verwenden, ergäbe das eine Laufzeit von ; insert, empty und decreaseKey lassen sich alle in realisieren, aber das Suchen des Elements mit der kleinsten Priorität erfordert eine lineare Suche mit .
Besser fährt man hier mit der Verwendung der DatenstrukturFibonacci-Heap. Diese ermöglicht es ebenfalls, die Operationen insert, empty und decreaseKey ( amortisiert betrachtet) in zu realisieren, die Komplexität von extractMin ist hier aber nur . Die gesamte Laufzeit beträgt dann lediglich .
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.
"Algorithmus von Dijkstra"
