Dijkstra Algorithmus
Du verstehst einfach nicht den Ablauf des Dijkstra-Algorithmus? Kein Problem! Wir schauen ihn uns Schritt für Schritt an.
Inhaltsübersicht
Der Algorithmus von Dijkstra
Der Dijkstra Algorithmus ist ein sogenannter Greedy Algorithmus . Er hilft dir die kürzesten beziehungsweise kostengünstigsten Wege zu berechnen. Die Kantengewichte , so nennt man die Kosten, um von einem Punkt zum nächsten zu kommen, dürfen beim Dijkstra-Algorithmus nicht negativ sein. Falls jedoch negative Kosten auftreten, solltest du besser den Bellman-Ford-Algorithmus anwenden.
Ablauf des Algorithmus von Dijkstra anhand eines Beispiels
Um den Dijkstra-Algorithmus zu verstehen schauen wir uns am besten ein konkretes Beispiel an!
Stell dir vor du planst deine nächste Reise. Die Frage ist, wie du deine möglichen Reiseziele am günstigsten erreichen kannst. Wie kommst du zum Beispiel am schnellsten von Nürnberg nach Kopenhagen? Indem du über Hamburg oder über Berlin fährst?
Schauen wir uns doch den Graphen einmal genauer an. Die Strecke AB hat ein Kantengewicht von 100. Das heißt du gelangst zu diesen Kosten von Ort A nach B.
Das wäre geklärt. Dann können wir jetzt damit starten das Beispiel per Hand durchzurechnen. Natürlich kannst du es auch in Java implementieren, den entsprechenden Pseudocode findest du unten in unserem Artikel.
Initialisierung
- Zuerst musst du den Algorithmus initialisieren.
- Am besten legst du eine Tabelle an, um den Überblick zu behalten. In die erste Spalte trägst du die jeweilige Iteration ein, in der du dich befindest. Für jeden Knoten gibst du dann die jeweiligen Kosten und den direkten Vorgänger In der letzten Spalte kannst du dein Vorgehen verwalten. Das hilft dir dabei einen guten Überblick zu haben.
- Die Kosten zum Startknoten betragen Null. Du bist ja schon zuhause.
- Zu deinen möglichen Reiseorten ist noch kein Weg bekannt. Darum bewertest du die Kosten erst einmal mit Unendlich. Das bleibt natürlich nicht so. Nach und nach werden diese Kosten verbessert.
- Jetzt benötigst du eine Warteschlange. In diese werden alle Knoten, die du bereits gefunden hast, eingefügt. Da du bisher nur deinen Startknoten kennst fügst du diesen als erstes in deine Warteschlange
Iteration 1
Kommen wir zur ersten Iteration.
- Da in der Warteschlange nur ein Element ist, wählst du dieses aus und betrachtest die direkten Nachfolger. Vom Startknoten aus können die Knoten B und D erreicht werden.
- Die Kosten, um vom Startknoten nach B zu kommen betragen 100. Als Vorgänger von Knoten B trägst du den Startknoten in deine Tabelle ein.
- Genauso gehst du mit Knoten D Die Kosten, um vom Startknoten nach D zu kommen betragen 50. Und als Vorgänger trägst du ebenfalls den ersten Knoten ein.
- Die Nachfolger des Startknotens hast du nun betrachtet. Du kannst ihn als erledigt markieren.
- Die beiden Nachfolgerknoten nimmst du in deine Warteschlange
Iteration 2
Weiter geht es mit Iteration 2.
- Nun wählst du den Knoten, den du mit den geringsten Kosten erreichst, aus deiner Warteschlange aus. Das ist hier Knoten D. Betrachte jetzt die Nachfolger.
- Die Kosten von Knoten B verändern sich nicht. Der direkte Weg vom Startknoten aus ist günstiger als der Umweg über Knoten D.
- Die neuen Kosten von Knoten E betragen jetzt 300. Trage auch hier den direkten Vorgänger
- Ergänze deine Warteschlange um den Knoten E. Knoten B ist ja bereits in der Warteschlange.
- Knoten D musst du von jetzt an nicht weiter betrachten und kannst ihn als erledigt markieren.
Iteration 3
Nach diesem Schema gehst du auch in der nächsten Iteration vor.
- Die Kosten, um Knoten C zu erreichen betragen 200 und der Vorgänger ist B.
- Bei Knoten E verändert sich nichts. Update auch hier deine Warteschlange indem du Knoten B als erledigt markierst und C in die Warteschlange aufnimmst.
Iteration 4
- In Iteration 4 werden die Nachfolger von Knoten C Das ist nur noch Knoten E. Doch du kannst erkennen, dass du Knoten E günstiger erreichst, wenn du den Weg über B und C wählst. Das heißt du erhältst neue Kosten von 250 und C als neuen Vorgänger.
- Auch Knoten E kannst du nun als erledigt
Iteration 5
Sehr gut! Du hast alle Knoten abgearbeitet! Somit kannst du keinen weiteren Knoten in die Warteschlange aufnehmen, sie ist also leer. Das führt zum Abbruch des Algorithmus.
Puuh das war jetzt ganz schön viel! Wir haben es auch gleich geschafft. Schauen wir uns nur noch kurz an was dir diese Tabelle nun eigentlich sagt. Das Ablesen aus der Tabelle erfolgt rekursiv: Nehmen wir uns zum Beispiel Knoten E genauer vor. Knoten E wird mit Gesamtkosten von 250 erreicht. Der Vorgänger ist Knoten C. Diesen erreichst du am besten über B. Und dorthin kommst du direkt vom Startknoten aus. Der kürzeste Weg vom Startknoten zu E führt also über Knoten B und C.
Top! Die nächsten Semesterferien können kommen! Denn genauso kannst du jetzt auch herausfinden wie du am besten von Nürnberg nach Kopenhagen kommst.
Super! Wir haben unser Beispiel durchgerechnet und du weist auch wie das Ergebnis aus der Tabelle abzulesen ist.
Pseudocode des Dijkstra Algorithmus
Du möchtest dir Arbeit sparen und den Dijkstra-Algorithmus nicht jedes Mal mühsam per Hand berechnen? Kein Problem! Du kannst ihn zum Beispiel in Java implementieren. Hilfreich ist dabei vorab ein Pseudocode des Algorithmus.
Initialisierung
Startknoten in Warteschlange W aufnehmen
Menge der erledigten Knoten E = ∅
Kosten des Startknotens mit 0 bewerten
Kosten für alle Knoten außer Startknoten mit ∞ bewerten
Iterationen
solange W ≠ ∅
wähle Knoten k mit den geringsten Kosten zum Startknoten
füge k zu W hinzu
berechne neue Kosten für alle Nachfolger j von k die nicht Element von E sind
falls Kosten zu j über k geringer sind
aktualisiere Kosten zu j
aktualisiere Vorgänger von j
füge j zu W hinzu
entferne k aus W
füge k zu E hinzu
wenn W = ∅
Algorithmus beendet