Dijkstra-Algorithmus
Findet den günstigsten Weg vom Start zum Ziel. Er nimmt immer den günstigsten Ort aus einer Prioritätswarteschlange, sodass sich die Kosten wie eine Flut vom Start aus ausbreiten.
- Zeit O((V + E) log V)
- Speicher O(V)
- nutzt eine Prioritätswarteschlange
Was bedeutet das?
- Kosten: was ein Schritt kostet. Im Labyrinth kostet Boden 1, Schlamm 3 und Wasser 9; im Graphen die Zahl an der Kante.
- Prioritätswarteschlange: eine Warteschlange, in der der Günstigste zuerst drankommt, nicht der Erste.
- Schätzung (h): eine Vermutung der restlichen Kosten. A* bleibt nur exakt, wenn sie nie zu hoch ist.
- Kante relaxieren: prüfen, ob der Weg über den aktuellen Ort einem Nachbarn günstigere Kosten gibt, und sie dann übernehmen.
- in der Warteschlange
- aktuell
- erledigt
- günstigster Weg
- Boden · 1
- Schlamm · 3
- Wasser · 9
- Wand
Neu: Start bei A1 mit Kosten 0. A1 ist der einzige Eintrag in der Warteschlange.
Leertaste: abspielen oder pausieren. Pfeiltasten links/rechts: Schritt. Pos1 und Ende: springen.
Probieren Sie es aus: Wähle den Sumpf. Der günstigste Weg führt ganz um den Schlamm herum: doppelt so viele Schritte wie die gerade Linie und trotzdem günstiger (34 statt 36).
So funktioniert es
Jeder Ort bekommt Kosten: 0 für den Start, unendlich für den Rest. Dijkstra hält die erreichten Orte in einer Prioritätswarteschlange und nimmt immer den günstigsten. Dessen Kosten stehen dann fest, denn jeder andere Weg dorthin müsste über etwas mindestens so Teures führen. Dann prüft er jeden Nachbarn: Ist der Weg über den gerade genommenen Ort günstiger als die bisherigen Kosten des Nachbarn, bekommt der Nachbar die neuen Kosten und merkt sich, woher er kam. Ist das Ziel genommen, führen diese Merker den günstigsten Weg zurück.
Wann es sich eignet
Dijkstra passt, wenn Schritte unterschiedlich viel kosten und keiner weniger als null: Straßenkarten und Navis, Routing in Netzwerken, die günstigste Flugverbindung. Kostet jeder Schritt gleich viel, liefert BFS dieselbe Antwort einfacher. Mit negativen Kosten kann Dijkstra falsch liegen; dafür gibt es Bellman-Ford.