Interaktive Demo
Dijkstra-Algorithmus
Edsger W. Dijkstra veröffentlichte seinen Algorithmus 1959. Er macht immer bei der günstigsten bisher gefundenen Zelle weiter, deshalb wächst seine Front nach Kosten statt nach Schritten, und er findet garantiert den günstigsten Weg.
Zeichne Wände oder Schlamm ins Gitter und ziehe Start und Ziel. Ist eine Suche fertig, wird nach jeder Änderung sofort neu gesucht. Male ein breites Band aus Schlamm: Darin wird die Front langsamer, und der Weg führt außen herum, wenn das günstiger ist. Jeder Schritt in den Schlamm hinein oder aus ihm heraus kostet mehr.
Ablauf
- Erweitert
- –
- Front (max.)
- –
- Wegkosten
- –
Drücke Abspielen oder Nächster Schritt, um die Suche zu starten.
Raster
Optionen
Legende
- Start (ziehen zum Verschieben)
- Ziel (ziehen zum Verschieben)
- Wand
- Schlamm
- Front (Open List)
- Besucht (Closed List)
- Gerade erweitert
- Weg
Eigenschaften
Optimal
Ja
Zellen werden in der Reihenfolge ihrer Kosten abgeschlossen, deshalb wird das Ziel über den günstigsten Weg erreicht.
Gewichtete Zellen
Ja
Kommt mit allen nicht negativen Kosten zurecht, wie dem Schlamm hier.
Heuristik
Nein
Kein Richtungssinn: Er sucht genauso viel vom Ziel weg wie zum Ziel hin.
Beliebiger Winkel
Nein
Bewegt sich von Zelle zu Zelle, gerade oder diagonal.
Alle Wegfindungsalgorithmen im Vergleich
| Algorithmus | Optimal | Gewichtete Zellen | Heuristik | Beliebiger Winkel |
|---|---|---|---|---|
| Breitensuche | Ohne Schlamm und Diagonalen | Nein | Nein | Nein |
| Tiefensuche | Nein | Nein | Nein | Nein |
| Dijkstra-Algorithmus diese Seite | Ja | Ja | Nein | Nein |
| Bidirektionale Suche | Ja | Ja | Nein | Nein |
| Gierige Bestensuche | Nein | Nein | Ja | Nein |
| A*-Suche | Mit Gewicht 1 und zulässiger Heuristik | Ja | Ja | Nein |
| Jump Point Search | Ohne Schlamm | Nein | Ja | Nein |
| Theta* | Nein | Abkürzungen nur über freies Gelände | Ja | Ja |
1. Eine Prioritätswarteschlange
- Gib dem Start die Kosten 0 und allen anderen Zellen unendliche Kosten.
- Nimm die Zelle mit den geringsten Kosten aus der Prioritätswarteschlange. Ihre Kosten stehen jetzt fest.
- Prüfe für jeden Nachbarn, ob der Weg über diese Zelle günstiger ist als der beste bekannte. Wenn ja, aktualisiere seine Kosten und seinen Vorgänger.
- Wiederhole das, bis das Ziel herausgenommen wird.
2. Kosten der Schritte
Ein Schritt kostet seine Länge (1, diagonal √2) mal das mittlere Gewicht der beiden Zellen: 1 auf freiem Gelände, 5 im Schlamm. Der Dijkstra-Algorithmus funktioniert mit allen Kosten, die nicht negativ sind.
3. Wo er verwendet wird
Routenplaner, Routing-Protokolle wie OSPF und viele Spiele nutzen den Dijkstra-Algorithmus oder seine Nachfahren. Er ist auch die Grundlage von A*, das eine Schätzung der restlichen Entfernung hinzufügt.
Quellen
- Edsger W. Dijkstra: A note on two problems in connexion with graphs (Numerische Mathematik, 1959).