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=
Am Beispiel von unbewerteten, ungerichteten, zusammenhängenden Graphen lassen sich viele Zusammenhänge zeigen, die auch auf geringeren Abstraktions- und Vereinfachungsstufen zutreffend sind.
==Definition kürzester Weg==
<p>In unbewerteten Graphen ist der kürzeste Weg von einem Knoten $u$ zu einem anderen Knoten $v$ derjenige, der nicht mehr Knoten enthält als ein beliebiger anderer Weg von $u$ zu $v$. Die Länge dieses Weges ist gleich die Anzahl der enthaltenen Kanten.</p>
[[Bild:Dreiwege.PNG]]
<p>Die beiden Wege $w(A,B,F)$ und $w(A, E, F)$ sind mit einer Länge von zwei jeweils gleich lang. Der Weg $w(A, C, D, F)$ hat eine Länge von drei. Für $w(A, C, D, F)$ gibt es also (mindestens) einen Weg, der Kürzer ist, für die beiden anderen Nicht. Es sind zwei gleichwertige kürzeste Wege unabhängig von der Darstellung, in der $w(A,B,F)$ die kürzeste Strecke zurücklegt.</p>
==Kürzeste Wege in speziellen Graphen==
<p>In Graphen, die bestimmte Eigenschaften aufweisen und in einer geeigneten (oft speicherintensiven) Datenstruktur hinterlegt sind, können kürzeste Wege teilweise sehr einfach gefunden werden</p>
===Bipartite Graphen===
{| class="wikitable"
|-
| [[Bild:Vollständig_bipartiter_Graph.PNG]] || [[Bild:Nicht_vollständig_bipartiter_Graph.PNG]]
|-
| <p>In einem vollständig bipartiten Graphen können kürzeste Wege bei geeigneter Speicherstruktur mit statischem Aufwand gefunden werden</p>|| <p>In nicht vollständig Bipartiten Graphen wird eine Nutzung der Eigenschaften deutlich schwieriger und wir greifen auf die allgemeine Herangehensweise zurück.</p>
|}
===Regelmäßige Gitter===
<p>In einem regelmäßigen Gitter gibt es eine große Anzahl gleichlanger Wege und damit auch eine große Anzah gleichwertiger kürzester Wege.</p>
[[Bild:Manhatten.PNG]]
<p>Die Abbildung zeigt ein regelmäßiges Gitter, in dem jeder Weg, der vom Startpunkt aus an jedem Knoten nur nach oben oder rechts führt, ein kürzester Weg ist. Allgemein gilt, dass in einem n-Dimensionalen regelmäßigen Gitter alle Wege zwiscen zwei Punkten kürzeste Wege sind, solange sie nur in jeweils eine der orthogonal aufeinanderstehenden Richtungspaaren führt.</p>
===Bäume===
<p>Die Suche nach kürzesten Wegen in Bäumen ist definitionsgemäß eqivalent mit der Suche nach dem allgemeinen Weg.</p>
<p>Im Fall eines ungerichteten, gewurzelten Baumes mit der Wurzel $w$ kann der (kürzeste) Weg zwischen $w$ und einen beliebigen Knoten $z$ bei geeigneter Datenstruktur mit einr Komplexität von $O(n)$ ermittelt werden, wobei $n$ der Grad von $z$ ist. Dies kann man sich zunutze machen, indem man für einen Graphen und den betrachteten Knoten einen Kürzeste-Wege-Baum aufstellt und dann für jeden beliebigen Punkt den kürzesten Weg von oder zu der Wurzel mit sehr geringem Aufwand findet</p>
{| class="wikitable"
|-
| [[Bild:Ursprungsgraph.PNG]] || [[Bild:K-W-Baum.PNG]] || [[Bild:Spannbaum.PNG]]
|-
| Allgemeiner Graph || Kürzester-Wege-Baum || Spannbaum, der kein Kürzeste-Wege-Baum ist
|}
<p>Jeder Kürzeste-Wege-Baum ist ein spannender Baum, aber mit Vorausblick auf gewichtete Graphen nicht unbedingt ein minimal spannender Baum. Umgekehrt ist auch nicht jeder spannende Baum ein Kürzeste-Wege-Baum</p>
==Kürzeste Wege im allgemeinen ungerichteten, unbewerteten Graphen==
[[Bild:Flhaje Allgemeiner ungerichteter, ungewerteter Graph.PNG]]
<p>In der oberen Graphik mit "nur" 48 Knoten und 55 Kanten kann der kürzeste Weg nicht mehr oder nur schwer durch "Scharfes Hinsehen" oder einfache Tricks gefunden werden. Bei mehr Katen und folglich mehr möglichen Wegen würde die Übersichtlichkeit sehr schnell viel schlechter werden. Wir benötigen ein allgemeingültiges Verfahren, um in jedem ungerichteten, unbewerteten Graphen den kürzesten Weg zwischen zwei Punkten zu finden.</p>
<p>Eine einfache Möglichkeit, mit Sicherheit den kürzesten Weg in einem unbewerteten Graphen zu finden, ist das Aufstellen eines Kürzeste-Wege-Baumes und die anschließende (sehr einfache) Suche nach dem Weg in diesem Baum.</p>
<popup name="Algorithmus">
Ziel: Suche nach dem Kürzesten Weg zwischen den Knoten $s$ und $z$ in einem zusammenhängenden, unbewerteten, ungerichteten Graphen
Inizialisiere eine Warteschlange mit dem Knoten $s$
Setze den Vorgänger von $s$ auf sich selbst
Solange das erste Element der $k$ der Warteschlange existiert:
Für jeden Knoten $l$, der über eine Kante mit einer $k$ verbunden ist:
Wenn $l$ nicht als "bearbeitet" oder "in Bearbeitung" markiert ist
Markiere $l$ als "in Bearbeitung"
Setze $k$ als den Vorgänger von $l$
Füge $l$ der Warteschlange hinzu
Setze $k$ als "bearbeitet"
Setzte $z$ als betrachteten Knoten $m$
Solange der Vorgänger von $m$ nicht $s$ ist
Füge $m$ dem Ergebnisweg hinzu
Setze den Vorgänger von $m$ als betrachteten Knoten
</popup>
<p>Dieser Algorithmus besitzt eine Komplexität von $O(n+m)$, da jeder Knoten nur einmal bearbeitet wird, jedoch für jede Kante zweimal geprüft wird, ob ein Knoten an dieser Kante in Bearbeitung oder breits bearbeitet ist.</p>
<p>Eine Verbesserung dieses Algorithmus bricht das Aufstellen des Kürzeste-Wege-Baumes ab, sobald $z$ als "bearbeitet" gesetzt wurde. Hierbei wird nur ein Teilbaum des Kürzeste-Wege-Baumes aufgestellt, doch der gefundene Weg ist in jedem Fall richtig.</p>
=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" (Bsp: Kilometerzahl | Durchschnittliche Fahrtzeit)
** 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]]
* $w =(v_s, d, c, g, f, h, v_z)$
* Länge $l = b(\{v_s,d\}) + b(\{d,c\}) + b(\{c,g\}) + b(\{g,f\}) + b(\{f,h\}) + b(\{h,v_z\})$
* Länge $l = 2 + 1 + 1 + 1 + 2 + 2$
* Länge $l = 9$
</popup>
* Wie kann man sicherstellen, dass dies tatsächlich der kürzeste Weg ist?
** Intuitive Lösung: Alle Längen der Wege berechnen
** $\rightarrow$ Dieser Brute-Force Ansatz ist vernichtend ineffizient,
** Betrachten Sie die folgende Darstellung, machen Sie sich die kombinatorische Explosion bewusst
** Sind Start und Zielknoten durch 30 Knotenpaare verbunden, gibt es hier über eine Milliarde Wege!
[[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)$
*Eine tabellarische Durchführung des Dijkstra-Algorithmus finden Sie in der zugehörigen [[Übung_Kürzeste_Wege_in_Graphen#.C3.9Cbung_2.1|Computerübung]]
* 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: bereits 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