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: Zulassen von Kantenbewertungen
• ermöglicht es Probleme realistischer zu modellieren
• Bspw. Navigationssysteme müssen "Kosten" in Betracht ziehen

Begriff "kürzester Weg"

• Mehrdeutigkeit

• • Präzisierung nötig

• Abhängig von Bewertung der Kanten

Definition Kürzester Weg in einem bewerteten Graphen ^{(Kripke, Röschke)}

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.