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

'''Dijksta-Algorithmus'''
Eingabe: Gewichteter Graph $G = (V,E)$ mit einem Startknoten $v_s \in V$ und $n$ Knoten und einer positiven Kantenbewertung

 1  Funktion Dijkstra(Graph, Startknoten):
 2      initialisiere(Graph,Startknoten,abstand[],vorgänger[],Q)
 3      solange Q nicht leer:                       // Der eigentliche Algorithmus
 4          u:= Knoten in Q mit kleinstem Wert in abstand[]
 5          entferne u aus Q                                // für u ist der kürzeste Weg nun bestimmt
 6          für jeden Nachbarn v von u:
 7              falls v in Q:
 8                 distanz_update(u,v,abstand[],vorgänger[])   // prüfe Abstand vom Startknoten zu v'
 9      return''' vorgänger[]