SS 2006: Wegeprobleme in Graphen (2V(+1Ü))

27.04.06

I. Kürzeste Wege: Eigenschaften und Algorithmen

Literatur

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. Lewandowski. Vereinheitlichte Darstellung von effizienten Techniken zur Kürzeste-Wege-Suche. Dissertation. Universität Stuttgart, 2005.
4. Schmid. Berechnung kürzester Wege in Straßennetzen mit Wegeverboten. Dissertation. Universität Stuttgart, 2000.
5. Turau. Algorithmische Graphentheorie. Addison-Wesley, 1996. (UB, Signatur: 4H 4990)

I.1 Eine kurze Geschichte der kürzesten Wege

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.

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

05.05.06

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

I.2 Entfernungskorrigierende Algorithmen

I.2.1 Verwaltung der Knotenmenge R als FIFO (Bellman-Ford) (Ablauf des Algorithmus in Phasen)

I.2.2 Phasen-Lemma: Sei w_k = v₀v₁...v_k, so gilt nach k Phasen, dass D(v_k) ≤ γ(w_k). Dies gilt auch, wenn der Graph negative Zyklen hat!

I.2.3 Korollar: Kürzeste Wege mit k Kanten sind nach k Phasen berechnet

I.2.4 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 )

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

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

12.05.06

I.2.6 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.2.7 Knoten-Verwaltung mit zwei Queues (Pallottino - Übung): 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 "nur" O( n²·m )

I.3 Entfernungssetzende Algorithmen

I.3.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.3.2 Invariante ∀ v ∈ R: D(v) = min { d(u) + γ(u,v) | u ∈ B }:

I.3.3 Korrektheit von I.3.1: Es existiert stets ein v ∈ R mit D(v) = d(v)

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

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

19.05.06

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

I.3.7 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.3.8 Das SSSP-Problem in Graphen mit γ ≥ 0 lässt sich in O( m + n·log n ) lösen: Dijkstras Algorithmus mit Fibonacci-Heaps (ohne Beweis / ohne Einführung der Datenstruktur)

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

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

I.3.11 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).

I.3.12 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)

26.05.06

I.3.13 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.3.7. 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.3.14 Sind die Kantengewichte positiv, so entspricht der A^*-Algorithmus mit Schätzfunktion konstant 0 dem Dijkstra-Algorithmus. Ist die Schätzfunktion dist(v,z), so werden die Knoten entlang der kürzesten Wege (zwischen v₀ und z) aufgenommen. (Hierbei können alle Knoten und Kanten zu kürzesten Wegen gehören, z.B. bei einem Gitter.)

I.3.15 Beim A^*-Algorithmus mit konsistenter Schätzfunktion werden die Knoten in aufsteigender Reihenfolge der Werte d()+ed() aufgenommen. Beweis: Übung!

I.3.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 R der Knoten, deren ausgehende Kanten noch betrachtet werden müssen, aufgenommen werden können.

I.3.17 Wird der Zielknoten beim A^*-Algorithmus erstmals aus der Menge R 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.3.18 Beispiel: Der Worst-Case für den A^*-Algorithmus mit zulässiger aber nicht konsistenter Schätzfunktion beträgt O(2ⁿ) Iterationen

I.4 Verwendung von Bucketstrukturen

I.4.1 Der Algorithmus von Dial: Speichere v mit D(v) im Bucket mit Index D(v). Insert/Decrease_Key benötigen je O(1), Delete_Min je Element O(1) und zusätzlich (summiert über alle Delete_Min-Aufrufe) max{d(v)|v∈V} → Gesamtlaufzeit O( m+n·γ_max ).

02.06.06

I.4.2 Intervalleigenschaft des Dijkstra-Algorithmus: Aufgrund der Invariante I.3.2 gilt max{D(v)|v∈R} ≤ min{D(v)|v∈R}+γ_max.

I.4.3 Korollar: Dials Algorithmus lässt sich mit γ_max+1 Buckets implementieren.

I.4.4 Weiter verringerter Platzbedarf bei Dials Algorithmus: Der Platzbedarf kann auf jede beliebige Konstante gedrückt werden, die Laufzeit erhöht sich dadurch asymptotisch nicht.

I.4.5 Eine √γ_max-Bucketstruktur: → Gesamtlaufzeit O( m+√n·γ_max ).

I.4.6 Goldbergs Caliberlemma:

I.4.7 D(v)=d(v) nach Dinitz

23.06.06

I.5 k-kürzeste Wege

I.5.1 Klassifizierung der k-kürzeste-Wege-Probleme

• uneingeschränkt (Zyklen sind in den k-kürzesten Wegen erlaubt)
• eingeschränkt (nur zyklenfreie Wege sind erlaubt)

I.5.2 Darstellung k-kürzester Wege: Der k-kürzeste-Wege-Baum

I.5.3 Der k-kürzeste Weg hat O(k·n) Kanten

I.5.4 Ein einfacher k-kürzeste-Wege-Algorithmus (Azevedo et.al.)

I.5.5 Eine Eigenschaft des (k+1)-kürzesten Weges: Der (k+1)-kürzeste Weg setzt sich stets aus einem (nicht verlängerbarem) Teil im k-kürzeste-Wege-Baum, einer von dort abzweigenden Kante und einem kürzesten Weg zum Zielknoten zusammen

30.06.06

I.5.6 Laufzeitverbesserung nach Martins et.al. und Lewandowski (verwendet I.5.5)

I.5.7 Das eingeschränkte k-kürzeste-Wege-Problem (Algorithmus von Yen)

30.06.06+07.07.06

II Berechnung kürzester Wege in Graphen mit verbotenen Strukturen (mit special Guest Dr. Wolfgang Schmid)

II.1 Der Hauptsatz der Abbiegeverbotstheorie
II.2 Kürzeste Wege in Graphen mit Abbiegeverboten (dynamische Verfahren)
II.3 Kürzeste Wege in Graphen mit Abbiegeverboten (statische Verfahren)
II.4 Der Beweis des Hauptsatzes
II.5 k-kürzeste Wege mit dem Algorithmus von Azevedo
II.6 Kürzeste Wege in Graphen mit Wegeverboten
II.7 Eine Beweisskizze des Algorithmus

14.07.06

III Ausgewählte Kapitel

III.1 Potentialfunktionenen

III.1.1: Definition: Potentialfunktion und reduzierte Kantengewichte

III.1.2: Invarianz bzgl. Zyklen negativer Länge

III.1.3: Invarianz bzgl. der Ordnung der Weglängen

III.1.4: Potentialfunktionen und Kürzeste-Wege-Bäume

III.1.5: Reduzierte Kantengewichte konsistenter Kanten

III.1.6: Ein Linearzeittest für D(·)=d(·) vgl. I.1.6 und I.1.7

III.1.7: Existenz konsistenter Potentialfunktionen

III.1.8: Ein einfacher Algorithmus für das APSP-Problem (Floyd)

III.1.9: Potentialfunktionen und das APSP-Problem

III.1.10: Dijkstra vs. A^* vs. Potentialfunktionen

21.07.06

III.2 Beidseitige Algorithmen

III.2.1: Ein Schema zur Lösung des SPSP-Problems durch beidseitige Suche

III.2.2: Ein Abbruchkriterium bei Verwendung von Dijkstras Algorithmus

III.2.3: Ein Abbruchkriterium bei Verwendung des A^*-Algorithmus

III.2.4: Beschleunigung durch Potentialfunktionen (nach Ikeda et.al.)

28.07.06

III.4 Skalierungstechniken (Algorithmus von Gabow)