Kürzeste Wege in Graphen
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
Kürzeste Wege in unbewerteten und bewerteten Graphen<br/>
Florian Haje, Alexander Preuß
=Kürzester Weg in unbewerteten Graphen=
=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
[[Datei:S3sademu_Bewerteter_ungerichteter_Graph.png|300px]]
==Begriff "kürzester Weg"==
* Was ist der kürzeste 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 [[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?
<popup name="Darstellung Graph G">[[Bild:Alpreu_Auk1.png]]</popup>
<popup name="Lösung"><!--[[Bild:Alpreu_Auk1-lsg.png]]-->Die Lösung wird später hier zu finden sein :) </popup>
* Wie kann man sicherstellen, dass dies tatsächlich der kürzeste Weg ist?
<!--CÜ * Intuitive Lösung: Alle Längen der Wege berechnen (Brute Force)-->
<!--CÜ [[Bild:Alpreu_Auk2.png]] -->
* 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>
: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)
* Spezielle Form der ''Breitensuche''
* Idee:
** vom Startknoten $v_s$ aus die kürzestmöglichen Wege weiterverfolgen
** durch "Update" längere Kanten ausschließen
* Gedankliche Vorstellung: Kugel-Faden-Gebilde
** Länge der Fäden entspricht Kantenbewertung
** Zur Bestimmung des kürzesten Weges von einer zur anderen Kugel hebt man eben diese an
** $\Rightarrow$ Straff gespannte Fäden zeigen den kürzesten Weg
'''Dijkstra-Algorithmus'''
Eingabe: Gewichteter Graph $G = (V,E)$ mit einem Startknoten $v_s \in V$, $n$ Knoten und nur positiven Kantenbewertungen
Ausgabe: Kürzeste-Wege-Baum vom Startknoten $v_s$ zu allen anderen Knoten $w \in V$
1 Setze $d(v, s)$ := 0, Vorgänger $(w)$ := NULL und $d(w)$ := $∞$ für alle $w ≠ v_s$
Setze Vorgänger $(v_s)$ := $v_s$
Setze $R$ := $\{v_s\}$
2 Wähle $w \in V \setminus R$ mit kürzester Entfernung zu $v_s$ und setzte $R$ := $R \cup \{w\}$
3 Für alle $u \in V \setminus R$, die mit $w$ verbunden sind, prüfe, ob die Entfernung von $u$ zum Startknoten größer ist
als die Summe der Entfernung zwischen $u$ und $w$ und der Entfernung zwischen $w$ und dem Startknoten. Setze in diesem
Fall $d(u)$ auf den Wert dieser Summe und den Vorgänger $(u)$ := $w$
4 Falls $V ≠ R$, gehe zu Schritt 2, ansonsten STOPP und Ausgabe aller Entfernungen $d(w)$
* Der Dijkstra Algorithmus findet mitunter auch mehrere (gleichwertige) Wege
* Man kann die Suche nach dem kürzesten Weg erst stoppen, wenn der Endknoten geupdated wurde
* Je nach Implementierung liegt die Komplexität bei <math>\mathcal{O}(n^2 + m)</math> oder <math>\mathcal{O}(n\cdot\log n + m)</math>
** Abhängig vom verwendeten Datentyp. $n$: Anzahl Knoten, $m$: Anzahl Kanten
* Ist ein Single-Source Shortest Path(SSSP)-Algorithmus
== Floyd&Warshall Algorithmus ==
* Ist ein All-Pairs Shortest Path(APSP)-Algorithmus
* Berechnet die kürzesten Wege zwischen '''allen''' knoten
* nach Robert Floyd (1936-2001) und Stephen Warshall (1935-2006)
* geht auf einen Kleene Algorithmus mit regulären Ausdrücken (1956) zurück
* 2 Teile: Floyd-Algorithmus und Warshall-Algorithmus
** Warshall-Algorithmus berechnet transitive Hülle
** Im Folgenden wird der Floyd-Algorithmus thematisiert
* Idee:
** Auf einem kürzesten Weg von K1 durch K2 zu K3 sind die enthaltenen Teilwege bereits minimal
** Kennt man die kürzesten Wege zwischen allen Knotenpaaren ($Index < X$), suche mit $Index <= X$
** Entweder: Weg über Knoten X (von K1 nach X nach K3) oder: bekannter Weg von K1 nach K3 (über Knoten mit $Index < X$)
'''Floyd-Algorithmus'''
Eingabe: Gewichtsmatrix $w$ des Graphen $G$
Ausgabe: Entfernung $d_i,_j$ zwischen den Knoten $v_i$ und $v_j$ für alle $i,j$
1 Für alle i,j setze die Entfernung d[i,j] := w[i,j]
2 Für k = 1 bis n
3 Für alle Paare i,j
4 Setze die Entfernung d[i,j] = min(d[i,j],d[i,k] + d[k,j])
5 (min ist Funktion zur Bestimmung des kleineren Wertes)
* Der Floyd-Algorithmus funktioniert auch bei Kanten mit negativem Gewicht
** Beispiel Taxifahrten (mit Kunde: positive Kante, ohne Kunde: negative Kante)
* Zyklen mit negativer Länge werden jedoch nicht erkannt (Bellman-Ford-Algorithmus)
* Der Algorithmus besitzt eine Komplexität von <math>\mathcal{O}(n^3)</math>
* Es ist einer der wenigen Graphalgorithmen die besser mit einer Matrix arbeiten als einer Liste
==Quellen==
* Wagenknecht, Algorithmen und Komplexität, 2003
* Krischke/Röpcke, Graphen und Netzwerktheorie: Grundlagen, 2015
* https://de.wikipedia.org/wiki/Algorithmus_von_Floyd_und_Warshall
* https://de.wikipedia.org/wiki/K%C3%BCrzester_Pfad
* http://fuzzy.cs.uni-magdeburg.de/studium/graph/txt/duvigneau.pdf