SS 2004: Wegeprobleme in Graphen (2V)

1. Ahuja/Magnanti/Orlin. Network flows. (Informatikbibliothek, Signatur: Ahuj-16727)
2. Cherkassky/Goldberg/Radzik. Shortest paths algorithms: Theory and experimental evaluation. Mathematical Programming 73 (1996), 129-174. Vorabversion: http://citeseer.ist.psu.edu/cherkassky93shortest.html
3. Turau. Algorithmische Graphentheorie. Addison-Wesley, 1996. (UB, Signatur: 4H 4990)

I.1 Eine kurze Geschichte der kürzesten Wege (Teil 1)

Literatur

• Ahuja/Magnanti/Orlin, Network flows (Kap. 4.3, 5.2, 5.3, 5.4, 5.5)
• (zum Teil auch in: Turau, Algorithmische Graphentheorie (Kap. 8.2, 8.3))

I.1.1 Klassifizierung der Kürzeste-Wege-Probleme

• SSSP: Single-Source Shortest-Path
• SPSP: Single-Pair Shortest-Path (auch OPSP (One-Pair), STSP (Single-Target))
• APSP: All-Pairs Shortest-Path

I.1.2 Definitionen

• gerichteter Graph G = (V,E,γ) mit Knotenmenge V ( n := |V| ) und Kantenmenge E ⊆ V×V ( m := |E| ),
  Kantengewichte γ : E→R⁺ (später auch γ : E→R, γ : E→N oder γ : E→Z)
• w = v₀v₁...v_k Weg mit Länge γ(w) := ∑^k_i=1 γ(v_i-1,v_i),
  |w| ist die Anzahl der Kanten im Weg w,
  w = v₀v₁...v_k heisst doppelpunktfrei gdw. v_i ≠ v_j für i ≠ j,
  w = v₀v₁...v_kv₀ heisst Zyklus
• v ist von u aus erreichbar gdw. es ex. Weg w = u...v,
  G = (V,E) ist stark zusammenhängend gdw. ∀ u,v ∈ V ∃ Weg w von u nach v
• T = (V,E_T) heisst (Spann-)Baum von G = (V,E), E_T ⊆ E mit Wurzel r ∈ V gdw. ∀ v ∈ V existiert ein eindeutiger Weg w = r...v
  (T hat keine Zyklen, jeder Knoten hat genau einen Vorgänger, die Wurzel hat keinen Vorgänger)

I.1.3 Notationen

• d_v0(v) := dist(v₀,v) - Länge eines kürzesten Weges von v₀ nach v
• D_v0(v) - Schätzungen für d_v0(v), in den Algorithmen gilt stets D_v0(v) ≥ d_v0(v) und gibt die bisher beste bestimmte obere Schranke für d_v0(v) an
• B_v0 ⊆ V - die Knoten, für die ein Algorithmus D_v0(v) = d_v0(v) schon berechnet hat (Baumknoten)
• R_v0 ⊆ V - Randknoten sind die Knoten, die über eine Kante von B_v0 erreichbar sind
  (dies entspricht den Knoten v ∈ V−B_v0 mit D_v0(v) < ∞)

I.1.4 Wiederholung des Dijkstra-Algorithmus

I.1.5 Teilwege kürzester Wege sind kürzeste Wege: w = v₀v₁...v_k ist kürzester Weg ⇒ w_ij = v_iv_i+1...v_j ist kürzester Weg

I.1.6 Eigenschaft der kürzesten Entfernungen: w = v₀v₁...v_k ist kürzester Weg ⇔ d(v_i) + γ(v_i,v_i+1) = d(v_i+1)

I.1.7 Existenz des Kürzeste-Wege-Baums: Sei G = (V,E,γ) ohne negative Zyklen, so existiert ein Spannbaum T = (V,E_T,γ_T) so, dass sich die kürzesten Entfernungen in G und T nicht unterscheiden. Sind die d(·) bekannt, so lässt sich T in O( n + m ) berechnen.

Hausaufgabe: Geben Sie Beispiele für Graphen ohne negative Zyklen an, für die der Graph, der die Kanten aller kürzesten Wege umfasst, Zyklen hat

I.1.8 Eine notwendige Bedingung für D(·) = d(·): ∀ (u,v) ∈ E: D(v) ≤ D(u) + γ(u,v), Kanten mit dieser Eigenschaft heißen konsistent (sonst verkürzend)

I.1.9 Hinreichende Bedingung für D(·) = d(·): D(v₀) = 0, ∀ v ∈ V: D(v) ≥ d(v), ∀ (u,v) ∈ E: D(v) ≤ D(u) + γ(u,v) ⇒ ∀ v ∈ V: D(v)=d(v)

I.1.10 Der generische Kürzeste-Wege-Algorithmus: Solange verkürzende Kanten (u,v) existieren, setze D(v) := D(u) + γ(u,v).
Laufzeit O( m·2ⁿ ), für ganzzahlige Kantengewichte O( n²·m·γ_|max| ).

27.04.04

I.1.11 Der modifizierte generische Kürzeste-Wege-Algorithmus: Verwalte in M die Knoten, die ausgehende verkürzende Kanten haben könnten. Algorithmus: Solange M ≠ ∅ entferne einen Knoten u ∈ M und setze für die ausgehenden verkürzenden Kanten (u,v) D(v) := D(u) + γ(u,v) und füge v zu M hinzu.
Laufzeit O( n·2ⁿ ), für ganzzahlige Kantengewichte O( n·m·γ_|max| ).

I.1.12 Verwaltung der Knotenmenge M als FIFO (Bellman-Ford)

I.1.13 Kürzesten Wege mit k Kanten sind nach k Phasen berechnet

I.1.14 Beispiel: Anzahl der Phasen kann kleiner als die Tiefe jedes Kürzeste-Wege-Baums sein

I.1.15 Laufzeit Bellman-Ford: Sei t die geringste Tiefe aller Kürzeste-Wege-Bäume, so löst Bellman-Ford in O( t·m ) das SSSP-Problem oder findet einen negativen Zyklus in O( n·m )

Hausaufgabe: Konstruieren Sie zu gegebenen n und m Graphen, die Θ( n·m ) Schritte brauchen

I.1.16 Beispiel: negative Zyklen: Lemma I.1.13 gilt auch für k ≥ n

I.1.17 Beispiel: Verbesserung durch Vorgängerheuristik: Wird v aus M entfernt und der Vorgänger vorg(v) ist in M, so hat sich D(vorg(v)) wieder verringert und die von v ausgehenden Kanten brauchen nicht betrachtet zu werden, da sich D(v) wieder verringern wird (spätestens, wenn vorg(v) aus M entfernt wird).

I.1.18 Knoten-Verwaltung als Deque (D'Esopo-Pape): Idee: Korrigiere falsch berechnete Teile so früh wie möglich, bevor mit noch nicht betrachteten Knoten weitergearbeitet wird: Knoten mit D(v) < ∞ werden vorne in die Deque (double ended queue) eingefügt (wie beim Stack), Knoten mit D(v) = ∞ hinten (wie bei einer Queue)
Laufzeit: Worst Case O( n·2ⁿ ), aber in der Praxis meist schneller als Bellman-Ford oder Dijkstra.

I.1.19 Worst-Case Beispiele

05.05.04

I.1.20 Knoten-Verwaltung mit zwei Queues (Pallottino): Idee wie bei D'Esopo-Pape, aber statt Deque (entspricht Kopplung von Stack und Queue) Verwendung einer weiteren Queue anstelle des Stacks für die wiederholt bearbeiteten Knoten.
Laufzeit: in der Praxis ähnlich schnell wie D'Esopo-Pape, aber Worst Case O( n²·m )

I.1.21 Aufteilung des Algorithmus von Pallottino in n mal Bellman-Ford

I.2 Eine kurze Geschichte der kürzesten Wege (Teil 2)

Literatur

• Ahuja/Magnanti/Orlin, Network flows (Kap. 4.4, 4.5, 4.7)
• Turau, Algorithmische Graphentheorie (Kap. 8.4, 8.6)

I.2.1 Generischer Kürzeste-Wege-Algorithmus mit optimaler Reihenfolge der Knotenauswahl: Bisher: Unnötiger Aufwand in den Algorithmen, da sich die D(v) verringern können, nachdem die von v ausgehenden Kanten schon konsistent gemacht wurden. Idee: Wähle den Knoten v so, dass D(v) = d(v) gilt.

I.2.2 Invariante ∀ v ∈ R: D(v) = min { d(u) + γ(u,v) | u ∈ B }: Damit existiert stets ein v ∈ R mit D(v) = d(v)

I.2.3 Das SSSP-Problem mit γ(u,v) = 1, (u,v) ∈ E lässt sich in O( n + m ) lösen: Beweis: Hausaufgabe!

I.2.4 Das SSSP-Problem in azyklischen Graphen lässt sich in O( n + m ) lösen

12.05.04

I.2.5 Dijkstras Algorithmus: Sei γ ≥ 0: Sei v ∈ R mit D(v) = min { D(v') | v' ∈ V−B }, so gilt D(v) = d(v)

I.2.6 Das SSSP-Problem in Graphen mit γ ≥ 0 lässt sich in O( n² ) bzw. O( m·log n ) lösen: Dijkstras Algorithmus mit Listen bzw. Heaps

I.2.7 Das SSSP-Problem in Graphen mit γ ≥ 0 lässt sich in O( m + n·log n ) lösen: Dijkstras Algorithmus mit Fibonacci-Heaps

I.2.8 Beim Dijkstra-Algorithmus werden die Knoten in aufsteigender Reihenfolge der Entfernung zum Startknoten betrachtet: Beweis: Hausaufgabe!

I.2.9 Jede vergleichsbasierte Implementierung von Dijkstras Algorithmus benötigt im Worst-Case Ω( m + n·log n ) Schritte: Rückführung auf das Sortierproblem

I.2.10 Definitionen für den A^*-Algorithmus: Eine Schätzfunktion ed_z : V→R heißt zulässig gdw. ed_z(v) ≤dist(v,z), v∈V. Sie heißt konsistent gdw. ed_z ist zulässig und ed_z(u) ≤ γ(u,v) + ed_z(v).

19+26.05.04

I.2.11 A^*-Algorithmus: Sei v ∈ R mit D(v) + ed_z(v) = min { D(v') + ed_z(v') | v' ∈ V−B }, so gilt D(v) = d(v)

I.2.12 Der A^*-Algorithmus mit konsistenter Schätzfunktion löst das SPSP- und das SSSP-Problem in O( m + n·log n ): Verwendung von Fibonacci-Heaps, sonst Laufzeiten wie in I.2.6. Entsprechen Kantenlängen und Schätzfunktion der Luftlinie, so beträgt die Laufzeit zur Lösung des SPSP-Problems im Mittel nur O(n) (Sedgewick/Vetter '86) - unabhängig von der Anzahl der Kanten!

I.2.13 Sind die Kantengewichte positiv so entspricht der A^*-Algorithmus mit Schätzfunktion konstant 0 dem Dijkstra-Algorithmus

I.2.14 Beispiel: Die Kantengewichte im A^*-Algorithmus können negativ sein! Die Laufzeit bleibt - konsistente Schätzfunktion vorausgesetzt - wie in I.2.12 angegeben.

Hausaufgabe: Überlegen Sie warum dies gilt (Auflösung am 2.6.)

I.2.15 Beim A^*-Algorithmus mit konsistenter Schätzfunktion werden die Knoten in aufsteigender Reihenfolge der Werte d()+ed() aufgenommen

I.2.16 Beispiel: Der A^*-Algorithmus mit zulässiger aber nicht konsistenter Schätzfunktion ist ohne Änderung nicht korrekt: Die D()-Werte der Baumknoten müssen sich wieder verringern dürfen und so diese Knoten wieder in die Menge M der Knoten, deren ausgehende Kanten noch betrachtet werden müssen, aufgenommen werden können.

I.2.17 Wird der Zielknoten beim A^*-Algorithmus erstmals aus der Menge M gewählt, so gilt D(z)=d(z), auch wenn die Schätzfunktion nur zulässig aber nicht konsistent ist: Dies ist eine wichtige Eigenschaft, da wir sonst gegenüber dem generischen Algorithmus keinen Vorteil hätten.

I.2.18 Beispiel: Der Worst-Case für den A^*-Algorithmus mit zulässiger aber nicht konsistenter Schätzfunktion beträgt O(n2ⁿ)

02.06.04

09.06.04

16.06.04

23.06.04

ab 30.06.04