Kurs:Algorithmen und Datenstrukturen/Vorlesung/Berechnung kürzester Weg Floyd-Warshall

Startseite

Vorlesung

1.Einleitung

2. Theoretische Grundlagen

2.1 Programmierparadigmen

2.2. Laufzeitanalysen

2.3. Entwurfsmuster

3. Suchen

3.1 Suchen in sortierten Folgen

3.2 Suchen in Texten

4. Sortieren

4.1 Algorithmen für vergleichsbasiertes Sortieren

4.2 Weitere Sortierprobleme

5. Dynamische Datenstrukturen

5.1 Binäre Suchbäume

5.2 AVL Bäume

5.3 2-3-4-Bäume und Rot-Schwarz Bäume

5.4 Heaps

5.5 Hashtabellen

6. Graphen

6.1 Einführung

6.2 Breitensuche

6.3 Tiefensuche

6.4 Topologisches Sortieren

6.5 Berechnung kürzester Wege

6.6 Berechnung maximaler Flüsse

6.7 Spannbäume

7. Optimierung

7.1 Grundlagen

7.2 Kombinatorische Optimierung

7.4 Lineare Optimierung

7.5 Simplex Verfahren

Floyd-Warshall

Auf dieser Seite wird der Floyd-Warshall Algorithmus behandelt. Der Dijkstras Algorithmus und Bellman-Ford berechnen zu einem gegebenen Startknoten die kürzesten Wege zu allen anderen Knoten (Single Source Shortest Paths – SSSP. Aber wie kann man die kürzesten Wege zwischen zwei Knoten v und w berechnen? Man könnte die bereits kennengelernten Algorithmen für jeden einzelnen Startknoten neu aufrufen, doch das geht auch geschickter. Hier kommt der Floyd-Warshall Algorithmus ins Spiel, welcher das All Pairs Shortest Path Problem löst. Zwar nicht unbedingt effizienter, aber eleganter. Dies geschieht nach dem Prinzip der dynamischen Programmierung.

Problemdefinition

Gegeben ist ein Graph G=(V,E). Wir möchten für jedes Paar $(v,w)\in V\times V$ den Wert D(v,w) eines kürzesten Pfades finden. Wir nehmen an, dass es keine negativen Kreise gibt.

Floyd Warshall

D	s	u	v	x	y
s	0	8	9	5	4
u	3	0	1	-2	-4
v	2	10	0	7	-5
x	6	3	4	0	-1
y	7	15	6	12	0

Idee

Die Grundidee des Floyd-Warshall Algorithmus ist, dass wenn ein kürzester Weg $\{(v,a_{1}),...,(a_{n},k),(k,a_{n+1}),...,(a_{m},w)\}$ von v nach w über k geht, dann gilt:

• $\{(v,a_{1}),...,(a_{n},k)\}$ ist ein kürzester Weg von v nach k
• $\{(k,a_{n+1}),...,(a_{m},w)\}$ ist ein kürzester Weg von k nach w

Im obigen Beispiel gilt folgendes:

• $s\to y:\{(s,x),(x,u),(u,v),(v,y)\}$
• $s\to u:\{(s,x),(x,u)\}$
• $u\to y:\{(u,v),(v,y)\}$

Die Umkehrung gilt jedoch nicht. Ist $\{(v,a_{1}),...,(a_{n},k)\}$ ein kürzester Weg von v nach k und ist $\{(k,a_{n+1}),...,(a_{m},w)\}$ ein kürzester Weg von k nach w dann gilt nicht notwendigerweise, dass $\{(v,a_{1}),...,(a_{n},k),(k,a_{n+1}),...,(a_{m},w)\}$ ein kürzester Weg von v nach w ist!

Im obigen Beispiel bedeutet dies:

• $x\to y:\{(x,y)\}$
• $y\to v:\{(y,v)\}$
• $x\to v:\{(x,y),(y,v)\}$ ist nicht der kürzeste Weg!

Jedoch gilt, wenn bekannt ist, dass ein kürzester Weg zwischen v und w nur Knoten aus $V'\subseteq V$ enthält, so gilt entweder der kürzeste Weg zwischen v und w benutzt nur Knoten aus $V'\backslash \{k\}$ oder der kürzeste Weg zwischen v und w ist Konkatenation aus dem kürzesten Weg zwischen v und k und dem kürzesten Weg zwischen k und w und beide Wege enthalten nur Knoten aus $V'\backslash \{k\}$.

$D^{V'}[i,j]=fac(x):=\left\{{\begin{array}{ll}\gamma (i,j)&falls~k=0\\min\{D^{V'\backslash \{k\}}[i,j],D^{V'\backslash \{k\}}[i,k]+D^{V'\backslash \{k\}}[k,j]\}&falls~k\geq 1\end{array}}\right.$

Algorithmus

algorithm FW(G)
   Eingabe: ein Graph G

   for each v,v‘∈V
      D[v,v‘] = γ((v,v‘)) (or ∞)
   for each k ∈ V do
      for each i ∈ V do
         for each j ∈ V do
            if D[i,k]+D[k,j] < D[i,j] then
               D[i,j] := D[i,k]+D[k,j]
            fi
         od
      od
   od

Beispiel

Initialisiere D mit den Kantengewichten. Nicht vorhandene Kanten haben das Gewicht $\infty$. Die Kantengewichte zum Knoten selber sind 0. Im folgenden betrachten wir nur Schleifendurchgänge mit $k\neq i,k\neq j,i\neq j$

Floyd Warshall

D	s	u	v	x	y
s	0	10	$\infty$	5	$\infty$
u	$\infty$	0	1	-2	$\infty$
v	$\infty$	$\infty$	0	$\infty$	-5
x	$\infty$	3	$\infty$	0	2
y	7	$\infty$	6	$\infty$	0

1: D[u,s]+D[s,v]<D[u,v]?

2: D[u,s]+D[s,x]<D[u,x]?

3: D[u,s]+D[s,y]<D[u,y]?

4: D[v,s]+D[s,u]<D[v,u]?

5: D[v,s]+D[s,x]<D[v,x]?

6: D[v,s]+D[s,y]<D[v,y]?

7: D[x,s]+D[s,u]<D[x,u]?

8: D[x,s]+D[s,v]<D[x,v]?

9: D[x,s]+D[s,y]<D[x,y]?

10: D[y,s]+D[s,u]<D[y,u]? → D[y,u]= D[y,s]+D[s,u]=7+10=17

D	s	u	v	x	y
s	0	10	$\infty$	5	$\infty$
u	$\infty$	0	1	-2	$\infty$
v	$\infty$	$\infty$	0	$\infty$	-5
x	$\infty$	3	$\infty$	0	2
y	7	17	6	$\infty$	0

11: D[y,s]+D[s,v]<D[y,v]?

12: D[y,s]+D[s,x]<D[y,x]? → D[y,x]= D[y,s]+D[s,x]=7+5=12

D	s	u	v	x	y
s	0	10	$\infty$	5	$\infty$
u	$\infty$	0	1	-2	$\infty$
v	$\infty$	$\infty$	0	$\infty$	-5
x	$\infty$	3	$\infty$	0	2
y	7	17	6	12	0

13: D[s,u]+D[u,v]<D[s,v]? → D[s,v]= D[s,u]+D[u,v]=10+1=11

Führt man den Algorithmus weiter durch, kommt man zu folgendem Endergebnis:

D	s	u	v	x	y
s	0	8	9	5	4
u	3	0	1	-2	-4
v	2	10	0	7	-5
x	6	3	4	0	-1
y	7	15	6	12	0

Analyse

Terminierungstheorem

Der Algorithmus FW(G) terminiert für eine endliche Eingabe G in endlicher Zeit. 

Beweis

Alle Schleifen sind endlich. 

Korrektheitstheorem

Ist G ein Graph, der keinen Zyklus mit negativem Gewicht hat, so enthält D nach Aufruf FW(G) die Distanzwerte von allen Knoten zu allen anderen Knoten.

Beweis

Betrachte dazu folgende Schleifeninvariante, die äußerste for-Schleife mit der Laufvariablen k): Nach der k-ten Schleifeniteration gilt, dass D[v,w], für alle v,w, der Wert eines kürzesten Pfades ist, der nur Knoten 1,...,k benutzt. Wenn der Algorithmus endet, gilt damit die Aussage des Theorems. Dies zeigen wir durch Induktion.

• k=0 (bei der Initialisierung): Nach der Initialisierung gilt D[v,w]= ∞ gdw. es keine Kante von v nach w gibt. Das bedeutet, dass jeder Pfad zwischen v und w mindestens einen anderen Knoten enthalten haben muss. Ist D[v,w] endlich, so ist dies genau der Wert der Kante. Dann gibt es also einen Pfad, der keine weiteren Knoten beinhaltet.
• k -> k+1: Nach der Induktionsannahme ist D[v,w] der Wert eines kürzestens Pfades, der nur Knoten aus 1,...,k enthält. Im k+1-Schleifendurchgang wird überprüft, ob es einen kürzeren Weg über k+1 gibt und ggfs. aktualisiert. Es wird also genau folgende Gleichung ausgenutzt:

$D^{V'}[i,j]=\left\{{\begin{array}{ll}\gamma (i,j)&{\text{falls}}\ V'=\emptyset \\min\{D^{V'\backslash \{k\}}[i,j],D^{V'\backslash \{k\}}[i,k]+D^{V'\backslash \{k\}}[k,j]\}&{\text{für}}\ k\in V'\end{array}}\right.$

Anschließend ist also D[v,w] der Wert eines kürzestens Pfades, der nur Knoten 1,...,k+1 benutzt.

Ein anderer Ansatz ist dies per Induktion nach der kürzesten Länge eines kürzesten Weges für jedes Knotenpaar (v,w) zu zeigen. Anmerkung: zwischen v und w können mehrere Wege mit minimalem Gewicht existieren, diese können auch unterschiedliche Länge haben. Angenommen zwischen v und w existiert ein kürzester Weg der Länge 1, dann ist der Wert dieses Weges gleich dem Wert der Kante (die existieren muss. Dieser wird in der Initialisierungsphase gesetzt und später nicht mehr geändert. Angenommen zwischen v und w gibt es einen kürzesten Pfad (=minimales Gewicht) der Länge l≥ 2 , dann gibt es einen Knoten k auf diesem Pfad, so dass zum einen der Teilpfad von v nach k ein kürzester Weg von v nach k ist und zum anderen, dass der Teilpfad von k nach w ein kürzester Weg von k nach w ist. Somit haben beide Pfade haben Länge < l, d.h. die Werte D[v,k] und D[k,w]  müssen schon korrekt berechnet sein (die Induktionsvoraussetzung greift). Da alle potentiellen “Mi5elknoten” überprüft werden,  wird ein geeignetes k gefunden und der Wert D[v,w] aktualisiert.

Laufzeittheorem

Sei G=(V,E,g) ein gerichteter Graph. Der Laufzeitaufwand vom Algorithmus von Floyd‐Warshall auf G ist $O(\mid V\mid ^{3}$).

Beweis

Einfache Schleifenanalyse.