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




Floyd-Warshall

Bearbeiten

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

Bearbeiten

Gegeben ist ein Graph G=(V,E). Wir möchten für jedes Paar   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

Die Grundidee des Floyd-Warshall Algorithmus ist, dass wenn ein kürzester Weg   von v nach w über k geht, dann gilt:

  •   ist ein kürzester Weg von v nach k
  •   ist ein kürzester Weg von k nach w

 

Im obigen Beispiel gilt folgendes:

  •  
  •  
  •  


Die Umkehrung gilt jedoch nicht. Ist   ein kürzester Weg von v nach k und ist   ein kürzester Weg von k nach w dann gilt nicht notwendigerweise, dass   ein kürzester Weg von v nach w ist!

Im obigen Beispiel bedeutet dies:

  •  
  •  
  •   ist nicht der kürzeste Weg!


Jedoch gilt, wenn bekannt ist, dass ein kürzester Weg zwischen v und w nur Knoten aus   enthält, so gilt entweder der kürzeste Weg zwischen v und w benutzt nur Knoten aus   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  .

 

Algorithmus

Bearbeiten
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

Bearbeiten

Initialisiere D mit den Kantengewichten. Nicht vorhandene Kanten haben das Gewicht  . Die Kantengewichte zum Knoten selber sind 0. Im folgenden betrachten wir nur Schleifendurchgänge mit  

 
Floyd Warshall
D s u v x y
s 0 10   5  
u   0 1 -2  
v     0   -5
x   3   0 2
y 7   6   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   5  
u   0 1 -2  
v     0   -5
x   3   0 2
y 7 17 6   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   5  
u   0 1 -2  
v     0   -5
x   3   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

Terminierungstheorem

Bearbeiten

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

Alle Schleifen sind endlich. 

Korrektheitstheorem

Bearbeiten

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.

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:

 

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

Bearbeiten

Sei G=(V,E,g) ein gerichteter Graph. Der Laufzeitaufwand vom Algorithmus von Floyd‐Warshall auf G ist  ).

Einfache Schleifenanalyse.