Kürzeste Wege in Graphen
Aus ProgrammingWiki
Archivierte Version vom 2015-11-08T17:15:59+00:00. Aktuelle Version
Inhaltsverzeichnis |
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.
*
A. Krischke, H. Röpcke in "Graphen und Netzwerktheorie"
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?
Darstellung Graph G
Lösung
Die Lösung wird später hier zu finden sein :)
- Wie kann man sicherstellen, dass dies tatsächlich der kürzeste Weg ist?