Kürzeste Wege in Graphen
Aus ProgrammingWiki
Archivierte Version vom 2015-11-07T11:37:48+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: 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*
- 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.
*
Kripke, Röschke in "Graphen und Netzwerktheorie"
Herangehensweise
- Wie geht man vor?
- Wann kann man einen Weg verwerfen?
- Wie könnte also ein Algorithmus aussehen?