Kürzeste Wege in Graphen

Aus ProgrammingWiki
Archivierte Version vom 2015-11-14T11:32:53+00:00. Aktuelle Version

Inhaltsverzeichnis

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

S3sademu_Bewerteter_ungerichteter_Graph.png


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?
Darstellung Graph G

Alpreu_Auk1.png

Lösung

Alpreu_Auk1-lsg.png


  • 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

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
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)


  • 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: 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