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) =�•

384

Beispiel

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

395

Approach: Transit-Node Routing[Bast, Funke, Matijevic, Sanders, Schultes]

s t

396

BeispielKarlsruhe ! Copenhagen

397

BeispielKarlsruhe ! Berlin

398

BeispielKarlsruhe ! Vienna

399

BeispielKarlsruhe ! Munich

400

BeispielKarlsruhe ! Rome

401

BeispielKarlsruhe ! Paris

402

BeispielKarlsruhe ! London

403

BeispielKarlsruhe ! Brussels

404

BeispielKarlsruhe ! Copenhagen

405

BeispielKarlsruhe ! Berlin

406

BeispielKarlsruhe ! Vienna

407

BeispielKarlsruhe ! Munich

408

BeispielKarlsruhe ! Rome

409

BeispielKarlsruhe ! Paris

410

BeispielKarlsruhe ! London

411

BeispielKarlsruhe ! Brussels

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]

413

BeispielKarlsruhe ! Berlin

414

BeispielKarlsruhe ! Berlin

415

BeispielKarlsruhe ! Berlin

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)

419

Beispiel: Transitknoten

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!

422

Kap. 11: Minimale Spannbäume

ab

c d

7

9

63

4

2

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