faecher:informatik:oberstufe:graphen:zpg:kuerzeste_pfade:kpfad_bellman_ford:start

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung
faecher:informatik:oberstufe:graphen:zpg:kuerzeste_pfade:kpfad_bellman_ford:start [14.02.2023 09:32] – sronfaecher:informatik:oberstufe:graphen:zpg:kuerzeste_pfade:kpfad_bellman_ford:start [15.02.2023 10:35] (aktuell) – sron
Zeile 25: Zeile 25:
  
 Gegeben ist ein Graph mit den Knoten A, B und C.  Gegeben ist ein Graph mit den Knoten A, B und C. 
-Kante AB hat Gewicht 3, Kante AC hat Gewicht 11 und Kante CB hat Gewicht -9.+Kante AB hat Gewicht 4, Kante AC hat Gewicht 10 und Kante CB hat Gewicht -8.
 Gesucht sind nun alle kürzestesten Wege von Knoten A aus. Gesucht sind nun alle kürzestesten Wege von Knoten A aus.
  
Zeile 32: Zeile 32:
 Nun überprüfen wir für jede Kante, ob es eine Abkürzung gibt. Nun überprüfen wir für jede Kante, ob es eine Abkürzung gibt.
   * 1. Phase   * 1. Phase
-Betrachte die Kante AB mit Gewicht 3. Addiere zum Kantengewicht die Kosten des Anfangsknoten der Kante (A) hinzu. +Betrachte die Kante AB mit Gewicht 4. Addiere zum Kantengewicht die Kosten des Anfangsknoten der Kante (A) hinzu. 
--> Weg von A nach B hat Kosten 3. Das ist kleiner als unendlich, somit werden die Kosten aktualisiert. +-> Weg von A nach B hat Kosten 4. Das ist kleiner als unendlich, somit werden die Kosten aktualisiert. 
-Notiere aktuellen Vorgänger von B.+Notiere den aktuellen Vorgänger von B.
  
 Betrachte nun die Kante von C nach B. Diese Kante startet bei einem Knoten, der aktuell keine kürzeste Distanz hat. Das bedeutet, diese Kante liefert keine Abkürzung. Betrachte nun die Kante von C nach B. Diese Kante startet bei einem Knoten, der aktuell keine kürzeste Distanz hat. Das bedeutet, diese Kante liefert keine Abkürzung.
  
-Betrachte abschließend die Kante AC. Die Distanz vom Ausgangsknoten plus das Kantengewicht ergibt 11. Auch hier aktualisieren wir die Distanz und den Vorgängerknoten.+Betrachte abschließend die Kante AC. Die Distanz vom Ausgangsknoten plus das Kantengewicht ergibt 10. Auch hier aktualisieren wir die Distanz und den Vorgängerknoten.
  
   * 2. Phase   * 2. Phase
 Prüfe jede Kante erneut. Prüfe jede Kante erneut.
-Starte wieder mit der Kante AB mit einem Gewicht 3. Hier ist die Summe von Anfangsknoten und Kantengewicht nicht kleiner als die bekannte Distanz - wir ändern also nichts.+Starte wieder mit der Kante AB mit einem Gewicht 4. Hier ist die Summe von Anfangsknoten und Kantengewicht nicht kleiner als die bekannte Distanz - wir ändern also nichts.
  
-Prüfe die Kante mit Gewicht -9. Distanz zum Ausgangsknoten von 11 plus -9 ergibt 2. Die Distanz sowie der Vorgänger werden aktualisiert.+Prüfe die Kante mit Gewicht -8. Distanz zum Ausgangsknoten von 10 plus -8 ergibt 2. Die Distanz sowie der Vorgänger werden aktualisiert.
  
   * 3. Phase   * 3. Phase
  • faecher/informatik/oberstufe/graphen/zpg/kuerzeste_pfade/kpfad_bellman_ford/start.1676367177.txt.gz
  • Zuletzt geändert: 14.02.2023 09:32
  • von sron