Kürzeste Wege in unbewerteten und bewerteten Graphen
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

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.

 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

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 \mathcal{O}(n^2 + m) oder \mathcal{O}(n\cdot\log n + m)
  • 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 \mathcal{O}(n^3)
• 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