Kürzeste Wege in Graphen
Aus ProgrammingWiki
Kürzeste Wege in unbewerteten und bewerteten Graphen
Florian Haje, Alexander Preuß
Inhaltsverzeichnis |
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
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.
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.
Kürzeste Wege in speziellen Graphen
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
Bipartite Graphen
 | 
|
| In einem vollständig bipartiten Graphen können kürzeste Wege bei geeigneter Speicherstruktur mit statischem Aufwand gefunden werden | In nicht vollständig Bipartiten Graphen wird eine Nutzung der Eigenschaften deutlich schwieriger und wir greifen auf die allgemeine Herangehensweise zurück. |
Regelmäßige Gitter
In einem regelmäßigen Gitter gibt es eine große Anzahl gleichlanger Wege und damit auch eine große Anzah gleichwertiger kürzester Wege.
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.
Bäume
Die Suche nach kürzesten Wegen in Bäumen ist definitionsgemäß eqivalent mit der Suche nach dem allgemeinen Weg.
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
 |  | 
|
| Allgemeiner Graph | Kürzester-Wege-Baum | Spannbaum, der kein Kürzeste-Wege-Baum ist |
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
Kürzeste Wege im allgemeinen ungerichteten, unbewerteten Graphen
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.
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.
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.
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.
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
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 $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?
- 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!
- 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
- $d(s, w)$ $≤$ $d(s, v)$ $+$ $b(\{v,w\})$
- erfüllt ist. Dabei bezeichnen $d(s, w)$ bzw. $d(s, v)$ jeweils die Entfernungen und $b(\{v,w\})$ die Bewertung 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 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
oder
- 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
- 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
