Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

--- graphen:breitensuche:dijkstra [2023/11/05 11:33] – [4. Schritt:] Martin Pabst
+++ graphen:breitensuche:dijkstra [2023/11/05 15:02] (aktuell) – [Dijkstra-Algorithmus] Martin Pabst
@@ Zeile 1: / Zeile 1: @@
 ====== Dijkstra-Algorithmus ======
+{{ youtube>GSlWaR9POvA?large }}
+ \\
 <WRAP center round todo 60%>
 {{ :graphen:breitensuche:pasted:20231105-113653.png?400}}
 Ein Navi findet in wenigen Sekunden die kürzeste Verbindung zwischen zwei Punkten. Wie macht es das? \\ \\
 Im Navi sind alle erreichbaren Orte als Knoten und die Wege zwischen ihnen als Kanten dargestellt. Die Kanten sind jeweils mit der Weglänge gewichtet. Schauen wir uns das Beispiel auf der rechten Seite an. Gesucht ist der kürzeste Pfad zwischen A und F. \\
-Die Lösungsidee besteht darin, von A ausgehend den Graphen so zu traversieren ("durchschreiten"), dass als nächstes immer der Knoten besucht wird, der von A die bisher kürzeste Entfernung hat. Wir legen uns dazu eine Tabelle an, in der wir zu jedem Knoten die länge des bisher kürzesten bekannten Pfades nach A notieren:
+Die Lösungsidee besteht darin, von A ausgehend den Graphen so zu traversieren ("durchschreiten"), dass als nächstes immer der Knoten besucht wird, der von A die bisher kürzeste Entfernung hat. Wir legen uns dazu eine Tabelle an, in der wir zu jedem Knoten die Länge des bisher kürzesten bekannten Pfades nach A notieren:
 {{ :graphen:breitensuche:pasted:20231105-113500.png?300 }}
 Bei A tragen wir zu Beginn gleich 0 ein, bei allen anderen Knoten den Wert ∞ (unendlich), da wir noch nicht wissen, wie lange der jeweils kürzeste Pfad zu A ist.
@@ Zeile 53: / Zeile 56: @@
   * Warum können wir ab jetzt sicher sein, dass der kürzeste Weg von A nach E derjenige über C mit Länge 8 ist? Formulieren Sie eine genaue Begründung unter Zuhilfenahme der zwei vorhergehenden gelben Kästen!
 </WRAP>
+==== 5. Schritt: ====
+{{ :graphen:breitensuche:pasted:20231105-123628.png?500}}
+  * Unter den noch nicht besuchten Knoten ist D der mit dem kürzesten Pfad zu A. Wir markieren ihn grün.
+  * Wir betrachten alle von D aus erreichbaren Knoten, die noch nicht besucht wurden (das ist nur noch F).
+    * Der Pfad von A über D nach F hat die Länge 14 und ist kürzer als der bisher kürzeste gefundene (14 < 15). Wer hätte das gedacht? => Tragen wir ein!
+==== 6. Schritt ====
+{{ :graphen:breitensuche:pasted:20231105-124059.png?500}}
+  * Unter den noch nicht besuchten Knoten ist F derjenige mit dem kürzesten Pfad zu A. Wir markieren ihn grün. \\ Hoppla, das ist ja der Zielknoten. => Wir sind fertig!
+<WRAP center round todo 60%>
+Unsere Aufgabe bestand darin, den kürzesten Weg von A zu F zu finden:
+  * a) Wir hatten am Ende alle Knoten besucht. Muss man immer alle Knoten eines Graphen besuchen, um den kürzesten Pfad von einem gegebenen Knoten zu einem anderen gegebenen Knoten zu finden? Falls "Nein": erweitern Sie den gegebenen Graphen um weiter Knoten und Pfade, so dass diese Knoten auf der Suche nach dem kürzesten Pfad von A nach F nicht besucht worden wären.
+  * b) Wir wissen jetzt, dass der kürzeste Pfad von A nach F die Länge 14 hat. Aber wie verläuft nun dieser Pfad? Ermitteln Sie den Pfadverlauf unter Verwendung der blau notierten Vorgängerknoten!
+</WRAP>