Kürzeste Wege in unbewerteten und bewerteten Graphen
Florian Haje, Alexander Preuß

Flo Teil

Alex Teil/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"

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

• 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, der n Knoten und nur positive Kantenbewertungen besitzt
  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 Setze R := \{v_s\}.