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"==

<!-- evtl. Bild Googleroute -->

* 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 [[Grundbegriffe_der_Graphentheorie_1#Knoten und Kanten|$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?

<!-- Bild aus Buch/random Website hier einfügen -->

<popup name="Darstellung Graph G"></popup>
<popup name="Lösung">Die Lösung wird später hier zu finden sein :)</popup>

<!-- CÜ: Lösung einfügen -->

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

<!-- CÜ: Antwort einfügen alle ausrechnen ("Brute Force")-->

<!-- Tafel Graph kombinatorische Explosion -->

<!-- CÜ: Bild einfügen? -->

* 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
::<span style="color:green;">$d(s, w)$</span> $≤$ <span style="color:maroon;">$d(s, v)$</span> $+$ <span style="color:purple;">$b(\{v,w\})$</span> 
<!-- $d(s, w) ≤ d(s, v) + b({v,w})$ -->
:erfüllt ist. Dabei bezeichnen <span style="color:green;">$d(s, w)$</span> bzw. <span style="color:maroon;">$d(s, v)$</span> jeweils die <span style="color:green;">Entfer</span><span style="color:maroon;">nungen</span> und <span style="color:purple;">$b(\{v,w\})$</span> die <span style="color:purple;">Bewertung</span> der Kante $\{v,w\}$.


* Das Optimalitätskriterium sagt aus, dass das Ersetzen einer Baumkante durch eine Nichtbaumkante nur zur Verlängerung (oder Gleichheit) der Weglänge führen kann.
* Wir müssen jedoch immer noch alle Nicht-Baumkanten überprüfen um sicher zu sein, dass es sich um den Kürzesten Weg handelt.

== Algorithmus von Dijkstra ==

* erfunden vom niederländischen Informatiker Edsger W. Dijkstra (1930-2002)
* Idee:
** vom Startknoten $v_s$ aus die kürzestmöglichen Wege weiterverfolgen
** durch "Update" längere Kanten ausschließen




<popup name="*">Definitionen nach A. Krischke, H. Röpcke in "Graphen und Netzwerktheorie"</popup>