Informatik 11

Diese Seite ist nicht editierbar. Sie können den Quelltext sehen, jedoch nicht verändern. Kontaktieren Sie den Administrator, wenn Sie glauben, dass hier ein Fehler vorliegt.

====== Aufgaben zum Dijkstra-Algorithmus ======
===== Aufgabe 1 =====
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.//
{{ :graphen:breitensuche:dijkstra_aufgabe_1.png?600 }}

[[.aufgabe1dijkstraloesung:start|Lösung]]

===== Aufgabe 2 =====
Kann man den Dijkstra-Algorithmus auch
  * für gerichtete Graphen
  * für unzusammenhängende Graphen
verwenden?

===== Aufgabe 3 =====
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?
{{ youtube>g_-VJP8IKU8?large }}
\\ 
\\ 
{{https://www.youtube.com/shorts/zxnX9vCykYU|Dijkstra Algorithm on a map}}

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

{{ youtube>ySN5Wnu88nE?large }}

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

{{ youtube>A60q6dcoCjw?large }}