Du verstehst einfach nicht den Ablauf des Dijkstra-Algorithmus? Kein Problem! Wir schauen ihn uns Schritt für Schritt an.
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.
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.
Kommen wir zur ersten Iteration.
Weiter geht es mit Iteration 2.
Nach diesem Schema gehst du auch in der nächsten Iteration vor.
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.
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.
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
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
Hallo, leider nutzt du einen AdBlocker.
Auf Studyflix bieten wir dir kostenlos hochwertige Bildung an. Dies können wir nur durch die Unterstützung unserer Werbepartner tun.
Schalte bitte deinen Adblocker für Studyflix aus oder füge uns zu deinen Ausnahmen hinzu. Das tut dir nicht weh und hilft uns weiter.
Danke!
Dein Studyflix-Team
Wenn du nicht weißt, wie du deinen Adblocker deaktivierst oder Studyflix zu den Ausnahmen hinzufügst, findest du hier eine kurze Anleitung. Bitte lade anschließend die Seite neu.