11   Kürzeste Pfade

Literatur: Teile von Kapitel 25/26 aus [CLR90]. [Ski97]

Inhalt Einleitung ·Varianten ·Relaxation ·Dijkstras Algorithmus ·Bellman-Ford ·lineare Programmierung

• Motivation: Routing, Streckenplanung
• klass. Beispiel für ein (gutartiges) Optimierungsproblem
• gegeben: gerichteter Graph mit Gewichtungsfunktion w: E ® R
• Problem: finde einen Verbindung/Pfad mit minimalen Kosten

• spezifizierte Quelle (single-source): finde einen kürzesten Pfad von einem gegeben Knoten für jeden Zielknoten
• spezifiziertes Ziel: (single-destination): duales Problem
• spezifizierte Quelle und Ziel (single-pair)
• kürzeste Pfade für alle Knotenpaare.

• Hier: single-source
• Eingabe: Gerichteter Graph G = (V,E) + Quelle s Î V.
• Ausgabe: nicht nur minimales Gewicht, sondern auch Pfad
• Þ Baum kürzester Pfade bei gegebenem Startknoten s:²⁰ G' = (V', E') mit:
  • V' Í V: Menge der von s aus erreichbaren Knoten
  • G': bewurzelter Baum mit Wurzel s
  • der (eindeutige, einfache) Pfad von s nach v in V' ist ein kürzester Pfad von s nach v in G.
• Repräsentierung: Im Lauf des Graphtraversierung: merke den Vorgänger p für jeden Knoten Þ G_p = (V_p, E_p).²¹
• Problem: Kanten mit negativen Kosten, insbesondere Zyklen mit negativen Kosten.

• Þ gutartiges Problem, viele Techniken anwendbar
  • greedy
  • Relaxation
  • dynamische Programmierung....

• Þ Zerlegung: Sei s v kürzester Pfad mit s u v, dann d(s,v) = d(s,u) + w(u,v).
• "`Dreiecksungleichung"'
  • d(s,v) £ d(s,u) + w(u,v) (mit (u,v) Î E)
  • d(s,v) £ d(s,u) + d(u,v)

• Methode zur Optimierung bei gutartigen Probleme
• pessimistische (worst-case) Abschätzungen
• im Laufe des Algos immer weiter verbessert
• gutartig: ``monoton'', neue Information verbessern die Schätzung nur
• für kürzeste Pfade: für alle v Î V: d(v) als obere Schranke für den Pfad von s nach v.

• generischer Relaxationsalgorithmus
  • Initialisierung: für all v Î V:
    • d(v) = ¥ (außer s)
    • d(s) = 0
    • p(V) = ^
  • Relaxierung einer Kante: Anwendung der Dreiecksungleichung: [mathescape=true,tabsize=2] Relax(v1, v2) = if d(v2) > d(v1) + w(v1,v2) then p(v2) := v1; d(v2) := d(v1) + w(v1,v2) fi <\code>
• Unterschiedliche Algorithmen, je nachdem wann und wieoft Kanten relaxiert werden.

Dijkstra

• Voraussetzung: nicht-negative Gewichtung
• S: Menge von Knoten, deren min. Gewicht bereits bestimmt ist: d.h. v Î S Þ d(v) = d(s,v)
• Hauptschritt:

  Nimm den Knoten u mit der momentan geringsten Pfadabschätzung aus V-S, relaxiere alle an u adjazierenden Knoten und stecke u nach S.

• Þ Hilfsstruktur: Priority Queue
• Greedy-strategie: relaxiere immer eine Kante zu dem unbehandelten Knoten mit dem geringsten Abschätzung des Abstandes.
• Graphsuche, gesteuert nach den besten Abschätzungen, Ähnlich Breitensuche
• Laufzeitkomplexität:
  • Jeder Knoten einmal aus der Queue genommen: O(V²)²²
  • jede Kante genau einmal relaxiert: O(E)
  • Þ O(V² + E) = O(V²).

Dijkstra (2)

---

Dijkstra(G,w,s)
  Intitialise(G,s);       // siehe generischer Algo.
  S := $\emptyset$;                 // Knoten mit bekannter Distanz 
  Q := V;                 // priority queue               

  while $Q \not= \emptyset$
  do
    u := extract-min(Q); 
    S := $S \cup \{u\}$;
    for all vertices $v  \in Adj(u)$
    do
        relax(u,v)
    done
  done
  

---

Bellmann-Ford

• beliebige Kantengewichtung, entdeckt negativ-gewichtete Zyklen
• Relaxation der Abschätzung des Abstandes.
• Laufzeitkomplexität: O(V E).
• Relaxation aller Kanten, ohne Berücksichtigung ihres Gewichtes, dafür genügend oft (d.h. keine greedy Strategie

Bellmann-Ford (2)

---

Bellmann-Ford(G,w,s)              // G = (V,E), Gewichtung w

  initialize(G,s);                // s. generischer Algo.
  for i := 1 to size(V)-1
  do
    for all edges $(u,v) \in  E$
    do 
      relax(u,v) 
    done
  done;
  for all edges $(u,v) \in E$     // Test auf negative Zyklen
  do
    if d(v) > d(u) + w(u,v) 
       then return false
       else return true
  done;

---

February 5, 2002

---