Dijkstra-Algorithmus
aus Wikipedia, der freien Enzyklopädie
Auch Link-State-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 Graphen mit negativen Gewichten aber ohne negative Zyklen ist der Bellman-Ford-Algorithmus geeignet.
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, dieser aber in der Knotenmenge selbst vorliegt. Dasselbe gilt auch für gerichtete, nicht stark zusammenhängende Graphen.
Inhaltsverzeichnis |
[Bearbeiten] Algorithmus
G bezeichnet einen gewichteten Graphen mit V als Menge von Knoten, E als Menge von Kanten 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.
Nach Ende des Algorithmus enthält d[v] die Abstände aller Knoten v zu s. In π[v] ist ein spannender Baum der von s aus ausgehenden minimalen Wege in Form eines In-Tree gespeichert.
Wird bei Erreichen von g abgebrochen, so enthalten d[v] und π[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
*/
reconstructShortestPath (n, p)
{
// Prüfe ob schon wieder beim Startknoten angekommen
while (π(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[v] := ∞
d[s] := 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 aktuelle
if d[v] > d[u] + w(u,v) {
// Neuer Weg kürzer als bisher gefundener Weg
// Aktualisiere geschätzte restliche Weglänge
d[v] := d[u] + w(u,v);
// Aktualisiere Vorgänger in kürzestem Pfad
π[v] := 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 * Q: Prioritätswarteschlange der Knoten, aufsteigend nach d-Werten sortiert */ Dijkstra (s, g, w, G) { 01 initialize(G, s); 02 Q := V[G]; // Füge alle Knoten aus dem Graph in die Warteschlange ein 03 while not isEmpty(Q) { 04 // Betrachte Knoten mit dem 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 := successors(u) do { 11 // relaxiere die Kante zwischen u und seinem Nachfolger 12 relax(u, v, w); 13 } 14 } 15 } 16 // Es konnte kein Pfad gefunden werden 17 return fail; 18 }
[Bearbeiten] 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 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.
[Bearbeiten] Grundlegende Konzepte und VerwandtschaftenDer 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. [Bearbeiten] Berechnung eines Spannbaumes 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 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 oder dem Algorithmus von Kruskal möglich. [Bearbeiten] ZeitkomplexitätIm 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 insg. n Knoten gibt, also 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), insg. ü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 Würde man zur Verwaltung der Knoten nun z.B. einfach eine Liste verwenden, ergäbe das eine Laufzeit von O(n2 + m); insert, empty und decreaseKey lassen sich alle in O(1) realisieren, aber das Suchen des Elements mit der kleinsten Priorität erfordert eine lineare Suche mit 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 O(1) zu realisieren, die Komplexität von extractMin ist hier aber nur O(logn). Die gesamte Laufzeit beträgt dann lediglich [Bearbeiten] AnwendungenRoutenplaner 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. [Bearbeiten] Andere Verfahren zur Berechnung kürzester PfadeWeiß 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. [Bearbeiten] Literatur
|
||||||||||||
.
.
