Die LKW-Fahrerin Frau Holms muss eine eilige Fracht von München nach Regensburg befördern. Wegen vieler Baustellen und Staus muss sie mit den im folgenden Graphen angegebenen Fahrzeiten rechnen. Ermitteln Sie mit Hilfe des Algorithmus von Dijkstra die zeitlich kürzeste Strecke!

Sie dürfen in der Lösung die Ortsnamen gerne durch deren Anfangsbuchstaben abkürzen.

Lösung

Kann man den Dijkstra-Algorithmus auch

• für gerichtete Graphen
• für unzusammenhängende Graphen

verwenden?

Nachfolgend sehen Sie zwei Animationen, die veranschaulichen, wie der Dijkstra-Algorithmus in einer großen Karte voranschreitet.

• Wenn sich der Abstand vom Startpunkt zum Zielpunkt verdoppelt, wie wird sich das vermutlich auf die Laufzeit des Algorithmus auswirken?
• Schlagen Sie vor, wie man den Algorithmus verändern könnte, so dass er bei realistischen Karten schneller zum Ziel findet. Findet der von Ihnen vorgeschlagene Algorithmus immer noch in jedem Fall den kürzesten Weg?

Dijkstra Algorithm on a map

Oft verwendet man statt des Algorithmus von Dijkstra eine Variante namens "A* Algorithmus". Hier ein Video dazu:

Hier noch eine interessante und weiterführende Interpretation des A*-Algorithmus