Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

--- graphen:breitensuche:dijkstra-aufgaben [2023/11/05 14:16] – [Aufgabe 1] Martin Pabst
+++ graphen:breitensuche:dijkstra-aufgaben [2023/11/06 11:12] (aktuell) – [Aufgabe 1] Martin Pabst
@@ Zeile 5: / Zeile 5: @@
 {{ :graphen:breitensuche:dijkstra_aufgabe_1.png?600 }}
-[[.aufgabe1dijkstraloesung:startx|Lösung]]
+[[.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 }}