Effiziente Algorithmen

Hartmut KlauckUniversität FrankfurtSS 0620.4.

Kürzeste Wege in gewichteten Graphen Gegeben sei ein Graph G als Adjazenzliste mit

Gewichten, d.h. für jede Kante (u,v) sei zusätzlich ein Gewicht W(u,v) gespeichert (wenn (u,v) keine Kante ist wird W(u,v)=1 gesetzt).

Wir suchen kürzeste Wege von einem Startknoten s zu anderen Knoten

Das Gewicht eines Weges von u nach v sei die Summe der Kantengewichte

Die Distanz von u und v sei das minimale Gewicht eines Weges von u nach v

Minimale Wege müssen nicht die wenigsten Kanten haben!

Varianten

Single-Source Shortest-Path:Finde von s aus kürzeste Pfade zu allen anderen Knoten

All-Pairs Shortest-Path:Finde die kürzesten Pfade zwischen allen Paaren von Knoten

Zuerst betrachte wir das SSSP Problem

Beobachtung

Wir betrachten Graphen ohne Zyklen negativer Länge

Betrachte einen minimalen Weg von s nach v

Dann gilt: Alle Teilwege beginnend ab s sind ebenfalls minimal

Idee für Algorithmen: Bestimme Wege mit weniger Kanten zuerst Wir benutzen Schätzungen d(v), zu

Anfang d(s)=0 und d(v)=1 sonst Erzeugen im Laufe des Algorithmus

bessere Schätzungen

Speicherung der Wege

Für jeden Knoten v speichern wir einen Vorgänger (v), zu Beginn ist dieser auf NIL gesetzt

Die Vorgänger sollen am Ende einen zur Wurzel s gerichteten Baum minimaler Wege bilden

Relaxierung einer Kante

Grundlegende Operation Relax(u,v,W)

• if d(v)>d(u)+W(u,v)then d(v):=d(u)+W(u,v); (v):=u

D.h. wenn es eine bessere Schätzung für v gibt, erneuere diese

Beobachtungen

Folgende Eigenschaften gelten für jede Folge von Relax Operationen 1. d(v) ¸ (s,v) zu jeder Zeit (per Induktion,

Übung)2. Somit: Knoten mit (s,v)=1 haben immer

d(v)=13. Sei s u v ein kürzester Pfad mit Endkante

(u,v) und d(u)=(s,u) zu einer Zeit. Nach Relaxierung der Kante (u,v) gilt d(v)=(s,v)• d(v)· d(u)+W(u,v) nach der Relaxierung

=(s,u)+W(u,v)=(s,v), wegen der Minimalität von Teilwegen

Dijkstras Algorithmus

Löst das single-source shortest-path problem Voraussetzung: W(u,v)¸ 0 für alle Kanten Idee: speichere Knoten so, dass Knoten mit

minimaler Distanzschätzung effizient ausgewählt werden können

Wähle einen solchen Knoten, relaxiere alle Kanten zu seinen Nachbarn

Bis alle Knoten ausgewählt Korrektheitsidee: für Knoten mit minimaler

Distanzschätzung ist diese bereits korrekt

Datenstruktur

Speichert n Knoten zusammen mit ihrem Distanzwert

Wir brauchen folgende Operationen: ExtractMin: Finde einen Knoten v mit

minimalem d(v), entferne ihn DecreaseKey(v,x): Ersetze die

Distanzschätzung von Knoten v durch x (x ist kleiner als bisherige Schätzung)

Initialisierung Diese Operationen reichen aus, um

Dijkstras Algorithmus zu implementieren

Dijkstras Algorithmus

Initialisiere (v)=NIL für alle v undd(s)=0, d(v)=1 sonst

S=; sei Menge der abgearbeiteten Knoten Q=V While Q;

u:=ExtractMin S:=S [ {u} und Q:=Q-{u} Für alle Nachbarn v von u:

Relax(u,v,W) • Relax benutzt DecreaseKey

Dijkstras Algorithmus

Arbeitsprogramm:

1. Beweise Korrektheit2. Implementiere die Datenstruktur3. Analysiere Laufzeit

3)Laufzeit

Die Laufzeit wird dominiert durch höchstens n ExtractMin Operationen und höchstens m DecreaseKey Operationen

2)

Werden später (!) eine Datenstruktur kennenlernen, die folgende Laufzeiten erlaubt: Amortisierte Zeit von ExtractMin ist

O(log n), d.h. Gesamtzeit für n Operationen O(n log n)

Amortisierte Zeit von DecreaseKey ist O(1), d.h. Gesamtzeit für m Operationen O(m)

Dies erlaubt Laufzeit von O(m+n log n)

Simple Implementierung

Speichere d(v) in einem Array DecreaseKey in O(1) ExtractMin in O(n)

Gesamtlaufzeit: O(n2) für ExtractMin und O(m) für DecreaseKey

Praktikabel für Adjazenzmatrizen

Korrektheit der Algorithmus Einige Beobachtungen

1. d(v) ¸ (s,v) zu jeder Zeit (per Induktion, Übung)

2. Somit: Knoten mit (s,v)=1 haben immer d(v)=1

3. Sei s u v ein kürzester Pfad mit Endkante (u,v) und d(u)=(s,u) zu einer Zeit. Nach Relaxierung der Kante (u,v) gilt d(v)=(s,v)

4. Wenn zu einer Zeit d(v)=1 für alle Knoten in V-S, dann sind diese Knoten alle nicht von s erreichbar

Korrektheit des Algorithmus Theorem: Dijkstras Algorithmus terminiert mit

d(v)=(s,v), d.h. die korrekten Distanzwerte werden berechnet. Invariante: Für alle v2 S gilt d(v)=(s,v) Zu Beginn ist S leer, daher stimmt die Invariante Zu zeigen ist, dass der nächste gewählte Knoten v

korrektes d(v) besitzt. Für s ist dies trivial wahr Für v s:

• Nur Knoten mit endlichem d(v) werden gewählt, oder die restlichen Knoten sind alle nicht von s erreichbar (und dann d(v) korrekt)

• Es gibt also einen (kürzesten) Weg von s nach v• Sei p ein solcher Pfad, und y der erste Knoten

ausserhalb von S auf diesem Pfad, x dessen Vorgänger

Korrektheit des Algorithmus

Behauptung: d(y)=(s,y), wenn v eingefügt wird Damit: d(v)· d(y)=(s,y)· (s,v). QED Zeigen Behauptung:

d(x)=(s,x) per Induktion Kante (x,y) wurde bereits relaxiert, d.h. nach

Beobachtung 3.) gilt d(y)=(s,y).

Korrektheit des Algorithmus Also ist zu jeder Zeit d(v) korrekt für alle

Elemente von S Am Ende des Algorithmus ist S=V, somit

sind alle Distanzen korrekt berechnet.

Noch zu zeigen: Auch die Wege selbst werden korrekt berechnet. Übung

Das single-source shortest-path Problem mit negativen Gewichten Gegeben Graph G, Gewichtsfunktion W

auf den Kanten, Startknoten s Ausgabe: Ein Bit, das anzeigt, ob ein

Zyklus negativer Länge von s erreichbar ist, wenn nicht, dann kürzeste Pfade von s zu allen anderen Knoten.

Bellman-Ford Algorithmus Initialisiere d(s)=0, d(v)=1 sonst For i=1 to n-1:

Relaxiere alle Kanten (u,v) Für jede Kante (u,v): wenn d(v)>d(u)

+W(u,v), Ausgabe: „es existiert ein negativer Zyklus“

Bemerkung: d(v) und (v) enthalten Distanz und Vorgänger

Laufzeit

Der Algorithmus läuft offensichtlich in Zeit O(nm)