Kürzeste Wege in unbewerteten und bewerteten Graphen
Florian Haje, Alexander Preuß

Flo Teil

Alex Teil/Kürzeste Wege in bewerteten Graphen

Wiederholung bewertete Graphen

• Wichtiger Unterschied zu unbewerteten Graphen: Zulassen von Kantenbewertungen
• ermöglicht es Probleme realistischer zu modellieren
• Bspw. Navigationssysteme müssen "Kosten" in Betracht ziehen

Begriff "kürzester Weg"

• Mehrdeutigkeit des Wortes "kürzester"
  • Präzisierung nötig
• abhängig von Bewertung der Kanten

Definition Kürzester Weg in einem bewerteten Graphen*

Es sei G = (V,E) ein bewerter, zusammenhängender Graph und es sei v_s ein Start- und v_z ein Zielknoten.

Ein Weg w = (v_s, ..., v_z) von v_s zu v_z heißt kürzester Weg, falls die Länge von w, also die Summe seiner Kantenbewertungen, verglichen mit jedem anderen Weg von v_s zu v_z minimal ist.

Herangehensweise

• Übung: Versuchen Sie den kürzesten Weg in der folgenden Darstellung des Graphen G zu finden.
  • Wie gehen Sie dabei vor?
  • Wann verwerfen Sie einen Weg?

• Wie kann man sicherstellen, dass dies tatsächlich der kürzeste Weg ist?

• Wir benötigen ein Optimalitätskriterium

Definition Kürzeste-Wege-Baum in einem bewerteten Graphen*

Ein Baum in einem (nur mit positiven Zahlen) bewerteten Graphen ist genau dann ein Kürzeste-Wege-Baum bez. eines Startknotens s, wenn für alle Nicht-Baumkanten {v,w} die Ungleichung

d(s, w) ≤ d(s, v) + b({v,w})

erfüllt ist. Dabei bezeichnen d(s, w) bzw. d(s, v) jeweils die Entfernungen und b({v,w}) die Bewertung der Kante {v,w}.