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

In der Pfingstwoche, sowie den Himmelfahrt/1.Mai/Fronleichnam-Wochen finden keine V/Ü statt. Planung für die verbleibenden Wochen:

17/18.4.

24/25.4.

8/9.5.

29/30.5.

5/6.6.

12/13.6.

19/20.6.

26/27.6.

3/4.7.

10/11.7.

17/18.7.

Do

V

V

V

V

V

V

V

V

V

V

V

Fr

-

V

Ü

Ü

-

Ü

-

Ü

-

Ü

-

Ausgabe der Übungen in der Vorlesung, Abgabe jeweils am Tag vor der Besprechung in der Vorlesung oder per E-Mail. Übungen: Blatt 1 (pdf), Blatt 2 (pdf), Blatt 3 (pdf), Blatt 4 (pdf), 05 (pdf)

Dies ist kein vollständiges Skript(!), gibt aber eine Übersicht über die behandelten Themen.

Hinweis zur Darstellung der mathematischen Symbole: Firefox und Opera zeigen alles korrekt an, IE zeigt alles lesbar an, sonstige Browser ... ?

Inhaltsverzeichnis

1. Kürzeste Wege: Eigenschaften und Algorithmen
   1. Wiederholung: Grundlegende Definitionen, Dijkstras Algorithmus.
      Generische Kürzeste-Wege-Algorithmen
   2. Entfernungskorrigierende Algorithmen: Bellman-Ford und Varianten (D'Esopo-Pape, Pallottino)
   3. Entfernungssetzende Algorithmen: SSSP in azyklischen Graphen, Dijkstras Algorithmus, A^*-Algorithmus
   4. Verwendung von Buckets (Algorithmen von Dial, Dinitz und andere Bucketstrukturen)
   5. k-kürzeste-Wege-Algorithmen
2. Ausgewählte Kapitel
   1. Potentialfunktionenen, Anwendung beim APSP-Problem, Dijkstra vs. A^*
   2. Skalierungstechniken (Algorithmen von Gabow und Goldberg)
   3. Wegeberechnung mit Abbiegeverboten

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 Techniken zur effizienten Kürzeste-Wege-Suche (pdf), ISBN 3-89959-339-1 @ Der Andere Verlag
4. Turau. Algorithmische Graphentheorie. Addison-Wesley, 1996. (UB, Signatur: 4H 4990)

17.04.08

I. Kürzeste Wege: Eigenschaften und Algorithmen

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 Wir betrachten im Folgenden stets Graphen ohne negative Zyklen

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

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.

24.04.08

I.1.12 Wird ein Knoten v mit D(v)=d(v) aus R gewählt, so wird v danach nie mehr zu R hinzugefügt

I.1.13 Bestimmung des Kürzeste-Wege-Baums mit Hilfe der pred(·)-Zeiger

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.5 Beispiel: Anzahl der Phasen kann kleiner als die Tiefe jedes Kürzeste-Wege-Baums sein

25.04.08

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

Eine andere Idee zur Verbesserung (erst korrigieren, dann weiterrechnen) führt auf die Algorithmen von D'Esopo-Pape und Pallottino.

I.2.7 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.8 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 "nur" O( n²·m )

08.05.08

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

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

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

29.05.08

Ausführungen zu I.3.8: → Fibonacci-Heaps (normalisierte Variante nach Takaoka): Definitionen (Rang), Operationen insert, decrease_key, delete_min, Eigenschaften (das i-te Kind hat Rang ≥i-2, ein Heap mit Rang i hat ≥F_i+2 Knoten (F_i ist die i-te Fibonacci-Zahl), der maximale Rang ist ≤ c·log(n)), amortisierte Zeitabschätzung, Beweis der amortisierten Laufzeiten O(1), O(1) und O(log(n))

05.06.08

I.3.9 Beim Dijkstra-Algorithmus werden die Knoten in aufsteigender Reihenfolge der Entfernung zum Startknoten betrachtet

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)

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 Beispiel: Die Kantengewichte im A^*-Algorithmus können negativ sein! Die Laufzeit bleibt - konsistente Schätzfunktion vorausgesetzt - wie in I.3.13 angegeben.

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

Einschub II.1 Potentialfunktionen

II.1.1 Potentialfunktion ist eine beliebige Abbildung π:V→R. Reduzierte Kantengewichte γ_π(u,v):=π(u)+γ(u,v)-π(v).

II.1.2 Eigenschaften von Potentialfunktionen: Für beliebige Wege w=v₀,v₁,...,v_k gilt γ_π(w)=∑^k_i=1 γ_π(v_i-1,v_i)=&pi(v₀);+γ(w)-π(v_k). Für beliebige Zyklen z=v₀,v₁,...,v_k,v₀ gilt γ_π(z)=∑^k_i=1 γ_π(v_i-1,v_i)+γ_π(v_k,v₀)=π(v₀)+γ(v₀,v₁,...,v_k)-π(v_k)+π(v_k)+γ(v_k,v₀)-π(v₀)=γ(z)
Korollar: G mit Gewichtsfunktion γ(·) hat genau dann negative Zyklen, wenn G_π mit Gewichtsfunktion γ_π(·) welche hat (π(·) kann dabei beliebig gewählt sein). Seien w₁ und w₂ zwei verschiedene Wege von u nach v mit γ(w₁)≤γ(w₂), so gilt auch γ_π(w₁)≤γ_π(w₂) für beliebige Potentialfunktionen π(·) - insbesondere ist ein kürzester Weg in G auch kürzester Weg in G_π.

II.1.3 Dijkstra vs. A^* vs. Potentialfunktionen: Der Ablauf des A^*-Algorithmus mit Schätzfunktion ed_z in G ist identisch mit dem Ablauf des Dijkstra-Algorithmus mit Potentialfunktion π=-ed_z in G_π
Deshalb läuft der A^*-Algorithmus auch mit negativen Kantengewichten schnell, wenn ed_z konsistent ist. Ist ed_z nicht konsistent, kann die Laufzeit wie beim Dijkstra-Algorithmus mit negativen Kantengewichten exponentiell werden (dazu müssen die Kantengewichte in G nicht negativ sein, eine nicht konsistente Schätzfunktion reicht aus).

12.06.08

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

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 Eine log(γ_max)-Bucketstruktur: → Gesamtlaufzeit O( m+n·log(γ_max) ).

19.06.08

I.4.7 Goldbergs Caliber-Lemma: Seien γ_min(v):=min{γ(u,v)} und D_min eine untere Schranke für min{D(v)|v∈R}, dann gilt für alle v∈R: D(v)≤D_min+γ_min(v)⇒D(v)=d(v)

1.4.8 Goldbergs Linearzeit-Algorithmus: Kombiniert man I.4.6 mit I.4.7, so ist der Erwartungswert der Laufzeit linear! (Prüfe bei jedem Umsetzen eines Knotens, ob das Caliber-Lemma gilt, und füge den Knoten ggf. dann in eine separate Liste; bei delete_min wähle bel. Knoten aus dieser Liste - nur wenn diese leer ist, normales delete_min durchführen und den Wert D_min neu setzen)

I.4.9 D(v)=d(v) nach Dinitz: Buckets bei reellwertigen Kantengewichten

Fortsetzung von II.1 Potentialfunktionen

II.1.4 Weitere Eigenschaften von Potentialfunktionen: mit π(·)=D(·) gilt γ_π(·)≥0 genau für die konsistenten Kanten und γ_π(·)<0 für die verkürzenden; mit π(·)=d(·) gilt stets γ_π(·)≥0; nur die Kanten mit γ_π(·)=0 können zum Kürzeste-Wege-Baum (bzgl. demselben Startknoten v₀) gehören (vgl. I.1.6 und I.1.7); mit π, so dass γ_π(·)≥0, können kürzeste Wege auch von beliebigen anderen Startknoten aus berechnet werden

II.1.5 Das APSP-Problem lässt sich in O(nm+ n²log(n)) lösen (Bestimmung einer geeigneten Potentialfunktion (Bellman-Ford mit virtuellem externen Startknoten) und n-faches Lösen des SSSP-Problems)

II.1.6 Das APSP-Problem lässt sich in beliebigen Graphen in O(n³) lösen (Standard-Algorithmus nach Floyd)

26.06.08

II.2 Skalierungstechniken (Algorithmen von Gabow und Goldberg)

II.2.1 Idee: Beschleunigung durch Approximation Laufzeit O(m·log(γ_max))

II.2.2 Algorithmus von Goldberg Laufzeit O(m·√n·log(|γ_min|))

03.07.08

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

10.07.08

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

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)

17.07.08

II.3 Berechnung kürzester Wege in Graphen mit Abbiegeverboten

II.3.1 Zyklenfreiheit und Teilwegeoptimalität ist in kürzesten Wegen unter Berücksichtigung von Abbiegeverboten nicht gewährleistet

II.3.2 Graphmodellierung nach Wattleworth und Shuldiner ('63): Ersetze jeden Knoten v durch einen Subgraphen mit je einem Knoten je eingehender und ausgehender Kante, verbinde diese neuen Knoten unter Berücksichtigung etwaiger Abbiegeverbote untereinander (ggf. leicht auch "Strafgewichte" für Links-Abbiegen o.ä. umsetzbar). Der modifizierte Graph G'=(V',E') hat n'=2m Knoten und m'=m+∑_v∈Vd⁺(v)·d^-(v)∈O(m·min{max{d⁺(V)},max{d^-(V)}})⊆O(nm) Kanten. Laufzeit von Dijkstra in G' mit Fibonacci Heaps O(nm), bei Straßengraphen (mit beschränktem Grad → m∈Θ(n)) beträgt die Laufzeit von Dijkstra in G' nur O(n·log(n)) (jedoch mit deutlich größeren Konstanten im Vergleich zum Ausgangsgraphen).

II.3.3 Kantenaufnahme nach Caldwell ('61): Dijkstra auf dem Dual-Graph (jede Kante wird zu einem (Dual-Graph-)Knoten; die Kantenpaare, deren Aufeinanderfolgen nicht durch ein Abbiegeverbot ausgeschlossen ist, werden mit (Dual-Graph-)Kanten verbunden. Ähnliche Abschätzung wie in II.3.2. - der Graph hat O(m) Knoten und O(nm) Kanten, Laufzeit allgemein O(nm), Laufzeit in Straßengraphen O(n·log(n)).

II.3.4 Beobachtung von Boroujerdi und Uhlmann ('98): Wird ein Dual-Graph-Knoten in II.3.3 zum ersten Mal in R aufgenommen, so kann sich dessen Wert D(·) danach nicht mehr verringern. Idee: Bereite in einem Preprocessing-Schritt für jeden Knoten (des Originalgraphen) die ausgehenden Kanten so auf, dass abhängig von der eingehenden Kante in O(log(n)+N) Zeit die N ausgehenden Kanten, die nicht mit der eingehenden Kante zusammen ein Abbiegeverbot bilden, berechnet werden können. Beim Bearbeiten einer Kante (= Dual-Graph-Knoten) wird diese dann aus dieser Datenstruktur in O(log(n)) gelöscht. Gesamtlaufzeit reduziert sich dann mit normalen Heaps auf O(m·log(n)).

II.3.5 Verbotsorientiertes Knotensplitting nach W. Schmid ('00): Für jede Kante (u,v), die zu einem Abbiegeverbot (u,v,w) gehört, füge einen Knoten v' hinzu, lösche die Kante (u,v), füge die Kante (u,v') hinzu, füge für jede Kante (v,x) mit x&neq;w eine Kante (v',x) hinzu (falls (v,x) nicht erste Kante eines Abbiegeverbots ist) oder eine Kante (v',x') hinzu (falls (v,x) erste Kante eines Abbiegeverbots ist). Existieren mehrere Abbiegeverbote (u,v,·), so müssen ggf. alle v' mit allen x' verbunden werden. Worst-Case wie oben, aber Graphzuwachs direkt abhängig von der Anzahl der Abbiegeverbote.