372
Dijkstra: Laufzeit
Function Dijkstra(s : NodeId) : NodeArray⇥NodeArrayd = {•, . . . ,•}; parent[s]:= s; d [s] := 0; Q.insert(s) // O(n)while Q 6= /0 do
u := Q.deleteMin // n⇥foreach edge e = (u,v) 2 E do // m⇥
if d [u]+ c(e)< d [v ] then // m⇥d [v ]:= d [u]+ c(e) // m⇥parent[v ] := u // m⇥if v 2 Q then Q.decreaseKey(v) // m⇥else Q.insert(v) // n⇥
return (d ,parent)
Insgesamt:
TDijkstra = O�
m ·TdecreaseKey(n)+n · (TdeleteMin(n)+Tinsert(n))�
373
Laufzeit
Dijkstras ursprüngliche Implementierung: „naiv“I insert: O(1) d [v ]:= d [u]+ c(u,v)
I decreaseKey: O(1) d [v ]:= d [u]+ c(u,v)
I deleteMin: O(n) d komplett durchsuchen
TDijkstra = O�
m ·TdecreaseKey(n)+n · (TdeleteMin(n)+Tinsert(n))�
TDijkstra59 = O(m ·1+n · (n+1))= O
�
m+n2�
374
Laufzeit
Bessere Implementierung mit Binary-Heap-Prioritätslisten:I insert: O(logn)I decreaseKey: O(logn)I deleteMin: O(logn)
TDijkstra = O�
m ·TdecreaseKey(n)+n · (TdeleteMin(n)+Tinsert(n))�
TDijkstraBHp = O(m · logn+n · (logn+ logn))= O((m+n) logn)
375
Laufzeit
(Noch) besser mit Fibonacci-Heapprioritätslisten:I insert: O(1)I decreaseKey: O(1) (amortisiert)I deleteMin: O(logn) (amortisiert)
TDijkstra = O�
m ·TdecreaseKey(n)+n · (TdeleteMin(n)+Tinsert(n))�
TDijkstraFib = O(m ·1+n · (logn+1))= O(m+n logn)
Aber: konstante Faktoren in O(·) sind hier größer!
376
Analyse im Mittel
Modell: Kantengewichte sind „zufällig“ auf die Kanten verteiltDann gilt:
E[TDijkstraBH(ea)p] = O⇣
m+n logn logm
n
⌘
Beweis: In Algorithmen II
377
Monotone ganzzahlige Prioritätslisten
Beobachtung: In Dijkstras Algorithmus steigt das Minimum in derPrioritätsliste monoton.
Das kann man ausnutzen. schnellere Algorithmenu.U. bis herunter zu O(m+n).
Details: in Algorithmen II
378
Negative KostenWas machen wir, wenn es Kanten mit negativen Kosten gibt?Es kann Knoten geben mit d [v ] =�•
s p vq ...Cs p vq
C (2)u u
Wie finden wir heraus, welche das sind?Endlosschleifen vermeiden!
379
Zurück zu Basiskonzepten (Abschnitt 10.1 im Buch)Lemma: 9 kürzester s–v -Pfad P =) P ist OBdA einfach(eng. simple)Beweisidee: (Kontraposition)Fall: v über negativen Kreis erreichbar )¬9 kürzester s–v -Pfad (sondern beliebig viele immer kürzere)
s p vq ...Cs p vq
C (2)u u
Sonst: betrachte beliebigen nicht-einfachen s–v -Pfad.Alle Kreise streichen einfacher, nicht längerer Pfad.
380
Mehr BasiskonzepteÜbung, zeige:
Teilpfade kürzester Pfade sind selbst kürzeste Pfade
a�b�c�d a�b,b�c ,c�d ,a�b�c ,b�c�d
Übung: Kürzeste-Wege-BaumAlle kürzeste Pfade von s aus zusammen bilden einen Baum, falls eskeine negativen Kreise gibt.
f
s
b
ed
c2
1
9
3 2
8
70
5
010
2
4
a5
6 6
7
381
Allgemeines Korrektheitskriterium
Sei R = h· · ·t1
z }| {
relax(e1) · · ·t2
z }| {
relax(e2) · · ·tk
z }| {
relax(ek) · · ·ieine Folge von Relaxationsoperationen undp = he1,e2, . . . ,eki= hs,v1,v2, . . . ,vki ein kürzester Weg.Dann gilt anschließend: d [vk ] = µ(vk)
Beweisskizze: (Eigentlich Induktion über k)
d [s] = µ(s) bei Initialisierungd [v1] = µ(v1) nach Zeitpunkt t1d [v2] = µ(v2) nach Zeitpunkt t2
· · ·d [vk ] = µ(vk) nach Zeitpunkt tk
382
Algorithmen brutal – Bellman-Ford-Algorithmus fürbeliebige Kantengewichte
Wir relaxieren alle Kanten (in irgendeiner Reihenfolge) n�1 mal.Alle kürzeste Pfade in G haben höchstens n�1 Kanten.) Jeder kürzeste Pfad ist eine Teilfolge dieser Relaxationen!
s=v
v
v
1
k3
2v=v
1. Runde
2. Runde
3. Runde(k−1). Runde
383
Negative Kreise finden
Nach Ausführung von Bellman-Ford:8 negativen Kreise C:9(u,v) 2 C :d [u]+ c(e)< d [v ]
Beweis: Übungv und alle von v erreichbaren Knoten x haben µ(x) =�•
385
Bellman-Ford – Laufzeit
O(nm), also viel langsamer als Dijkstra!
Es gibt Algorithmenvarianten mit viel besserem best case.
386
Azyklische Graphen (10.2 im Buch)Beobachtungen:
Keine (gerichteten) Kreise =) keine negativen Kreise!Für jeden (kürzesten) Pfad hv1, . . . ,vni:Die Kanten sind aufsteigend bzgl. jeder topologischen Sortierung!
initialize d , parentforeach v 2 V in topological order do scan(v)
Laufzeit: O(m+n)
3
9
s
1
4
52 7
68
387
Von überall nach überallIm Prinzip: n⇥ von s nach überallnichtnegative Kantengewichte: Zeit O(n(m+n logn)).(n⇥ Dijkstra)
beliebige Kantengewichte: Zeit O�
n2m�
.(n⇥ Bellman-Ford)In Algorithmen II: Zeit O(n(m+n logn)).(1⇥ Bellman-Ford + n⇥ Dijkstra)
388
Kürzeste Wege: Zusammenfassung
I Einfache, effiziente Algorithmen für nichtnegative Kantengewichteund azyklische Graphen
I Optimale Lösungen bei nicht (ganz) trivialen KorrektheitsbeweisenI Prioritätslisten sind wichtige Datenstruktur
389
Mehr zu kürzesten Wegen
Viele Arbeiten zu besseren Prioritätslisten O(m+n log logn) [Thorup 2004]I Mehrere Zielfunktionen abwägenI Mehrere Ziele in beliebiger Reihenfolge anfahren
siehe auch OptimierungskapitelI Mehrere disjunkte Wege
Fast alles schwierig (NP-schwer)
390
Exkurs: Routing in StraßennetzwerkenStart: Beobachtungen zu Eigenschaften von Straßennetzwerken
I groß, z.B. n =18 000 000 Knoten für WesteuropaI dünn besetzt, z.B., m =⇥(n) KantenI beinahe planar, d.h., wenige Kanten kreuzen sich (Brücken)I inhärente Hierarchie, schnellste Pfade benutzen wichtige Straßen
391
Straßennetzwerke
Gängige Anwendungen:I Routenplanungssysteme im Internet, (z. B. www.map24.de)I FahrzeugnavigationssystemeI LogistikI Verkehrssimulationen
392
Distanz zu einem Zielknoten t
Was machen wir, wenn wir nur die Distanz von s zu einembestimmten Knoten t wissen wollen?
Trick 0: Dijkstra hört auf, wenn t aus Q entferntwird.Spart “im Durchschnitt” Hälfte der Scans.
ts
Frage: Wieviel spart es (meist) beim Europa-Navi?
393
Ideen für Routenplanungmehr in Algorithmen II, Algorithm Engineering
I Vorwärts- + Rückwärtssuche
ts
I Zielgerichtete Suchets
I Hierarchien ausnutzen
s t
I Teilabschnitte tabellieren
s z
Meist zentrale Idee: Vorberechnung amortisiert über viele Anfragen
394
Straßennetzwerke
Wir konzentrieren uns aufStraßennetzwerke.I mehrere nützliche
Eigenschaften, die sichausnutzen lassen
I viele reale Anwendungen
I einige Techniken: anwendbar füröffentliche Verkehrsmittel
I die meisten Techniken: unklar, wienützlich sie für weitere Graphtypensind
412
Erste Beobachtung
Lange Strecken benutzen
nur wenige ‘wichtige’ Zugänge zum Fernverkehrsnetzwerk,sog. access points
( wir können alle Zugangspunkte vorberechnen)
[in Europa: etwa 10 Zugangspunkte pro Knoten im Mittel]
416
Zweite Beobachtung
Jeder Zugangspunkt ist für mehrere Knoten relevant.
Gesamtmenge aller Zugangspunkte ist klein,Transitknotenmenge
( wir können alle Abstände zwischen allen Transitknoten speichern)
[in Europa: ⇡ 10 000 Transitknoten]
417
Transit-Node Routing
Preprocessing:I Identifiziere Transitknoten T ✓ V
I Berechne |T |⇥ |T | AbstandstabelleI Für jeden Knoten: identifiziere Zugangsknoten
(Abbildung A : V ! 2T ),speichere Abstände
Query (geg. Start s und Ziel t): berechne
dtop(s, t) := min{d(s,u)+d(u,v)+d(v , t) : u 2 A(s),v 2 A(t)}
418
Transit-Node Routing
Lokalitätsfilter:lokale Fälle ausfiltern ( Spezialbehandlung)
L : V ⇥V ! {true, false}
¬L(s, t) impliziert d(s, t) = dtop(s, t)
420
Experimente
I sehr schnelle Anfragen (queries)(4 µs, > 1 000 000 mal schneller als Dijkstra)
I Gewinner der 9. DIMACS Implementation ChallengeI erträglich: Vorberechnungszeiten (1:15 h) und
Speicherbedarf (247 bytes/Knoten)
I Neuere Werte: < 2µs, 5 Minuten PP, 150 Bytes/Knoten
s t
420
Experimente
I sehr schnelle Anfragen (queries)(4 µs, > 1 000 000 mal schneller als Dijkstra)
I Gewinner der 9. DIMACS Implementation ChallengeI erträglich: Vorberechnungszeiten (1:15 h) und
Speicherbedarf (247 bytes/Knoten)I Neuere Werte: < 2µs, 5 Minuten PP, 150 Bytes/Knoten
s t
421
Offene Fragen
I Wie bestimmt man die Transitknoten?I Wie bestimmt man die Zugangsknoten effizient?I Wie bestimmt man die Lokalitätsfilter?I Wie handhabt man lokale Anfragen?
Antwort:I Andere Routenplanungstechniken benutzen!
423
Minimale Spannbäume (MST)
Eingabe:
I ungerichteter (zusammenhängender) Graph G = (V ,E ).I Knoten V , n = |V |, z. B. V = {1, . . . ,n}I Kanten e 2 E ✓ V ⇥V , m = |E |I Kantengewichte c(e) 2 R+.
4
2
3
1
792
5
Aufgabe:Finde Baum (V ,T ) mit minimalem Gewicht Âe2T c(e),der alle Knoten verbindet.
423
Minimale Spannbäume (MST)
Eingabe:
I ungerichteter (zusammenhängender) Graph G = (V ,E ).I Knoten V , n = |V |, z. B. V = {1, . . . ,n}I Kanten e 2 E ✓ V ⇥V , m = |E |I Kantengewichte c(e) 2 R+.
4
2
3
1
792
5
Aufgabe:Finde Baum (V ,T ) mit minimalem Gewicht Âe2T c(e),der alle Knoten verbindet.
424
Minimale spannende Wälder (MSF)
Falls G nicht zusammenhängend ist,finde minimalen spannenden Wald T , der alleZusammenhangskomponenten von G aufspannt.
MST-Algorithmen lassen sich leicht zu MSF-Algorithmenverallgemeinern.
425
Anwendungen
I Netzwerk-EntwurfI Bottleneck-Shortest-Paths:
Suche s–t-Pfad, dessen max.Kantengewicht minimal ist.Dies ist der Pfad im MST!
I Clustering: Lass schwere MST-Kantenweg. Teilbäume definieren Cluster.Konkret z. B. Bildsegmentierung
I Näherungslösungen für schwereProbleme, z. B. Handlungsreisenden-,Steinerbaumproblem.Siehe Buch, VL G. theoretischerInformatik, Algorithmen II.
I Irrgärten (Beispiel von Wikipedia)
4
2
3
1
792
5
425
Anwendungen
I Netzwerk-EntwurfI Bottleneck-Shortest-Paths:
Suche s–t-Pfad, dessen max.Kantengewicht minimal ist.Dies ist der Pfad im MST!
I Clustering: Lass schwere MST-Kantenweg. Teilbäume definieren Cluster.Konkret z. B. Bildsegmentierung
I Näherungslösungen für schwereProbleme, z. B. Handlungsreisenden-,Steinerbaumproblem.Siehe Buch, VL G. theoretischerInformatik, Algorithmen II.
I Irrgärten (Beispiel von Wikipedia)
4
2
3
1
792
5
425
Anwendungen
I Netzwerk-EntwurfI Bottleneck-Shortest-Paths:
Suche s–t-Pfad, dessen max.Kantengewicht minimal ist.Dies ist der Pfad im MST!
I Clustering: Lass schwere MST-Kantenweg. Teilbäume definieren Cluster.Konkret z. B. Bildsegmentierung
I Näherungslösungen für schwereProbleme, z. B. Handlungsreisenden-,Steinerbaumproblem.Siehe Buch, VL G. theoretischerInformatik, Algorithmen II.
I Irrgärten (Beispiel von Wikipedia)
4
2
3
1
792
5
426
MST-Kanten auswählen und verwerfenDie Schnitteigenschaft (Cut Property)
Für beliebige Teilmenge S ⇢ V betrachtedie SchnittkantenC = {{u,v} 2 E : u 2 S ,v 2 V \S}
Die leichteste Kante in Ckann in einem MST ver-wendet werden. 4
2
3
1
72
5
9
426
MST-Kanten auswählen und verwerfenDie Schnitteigenschaft (Cut Property)
Für beliebige Teilmenge S ⇢ V betrachtedie SchnittkantenC = {{u,v} 2 E : u 2 S ,v 2 V \S}
Die leichteste Kante in Ckann in einem MST ver-wendet werden.
Beweis: Betrachte MST T 0.Fall e 2 T 0: Beweis fertig.Sonst: T 0 [{e} enthält Kreis K .Betrachte eine Kante {u,v} 2 C \K 6= e.Dann ist T = T 0 \{{u,v}}[{e} einSpannbaum, der nicht schwerer ist.Denn: c(e) c({u,v})
V\S
V\S
S
S
e
e
(u,v)
(u,v)
427
MST-Kanten auswählen und verwerfenDie Kreiseigenschaft (Cycle Property)
Die schwerste Kante auf einem Kreis wird nicht für einen MST benötigt.
4
2
3
1
792
5
427
MST-Kanten auswählen und verwerfenDie Kreiseigenschaft (Cycle Property)
Die schwerste Kante auf einem Kreis wird nicht für einen MST benötigt.
Beweis.
Angenommen, MST T 0 benutzt die schwerste Kante e 0 auf Kreis C .Wähle e 2 C mit e 62 T 0.Es gilt c(e) c(e 0).Dann ist T = T 0 \{e 0}[{e} auch ein MST.
4
2
3
1
792
5