Kürzeste Wege in Graphen

Wiki-Quelltext dieser Seite.

Kürzeste Wege in unbewerteten und bewerteten Graphen<br/>
Florian Haje, Alexander Preuß

=Flo Teil=

=Alex Teil/Kürzeste Wege in bewerteten Graphen=
==Wiederholung bewertete Graphen==
<!-- Hier Bild einfügen -->
* 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
<!-- evtl. Bild Googleroute -->
** Präzisierung nötig
<!-- Beispiel bringen -->
* 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.
<popup name="*">Kripke, Röschke in "Graphen und Netzwerktheorie"</popup>

==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?
<!-- Bild aus Buch/random Website hier einfügen -->
<popup name="Lösung">Die Lösung wird später hier zu finden sein :)</popup>
* Wie kann man sicherstellen, dass dies tatsächlich der kürzeste Weg ist?