Aktuelle Version vom 10. März 2009, 19:04 Uhr

Floyd-Warshall

Eigenschaften

Der Floyd-Warshall-Algorithmus (benannt nach Robert Floyd und Stephen Warshall) findet nicht nur den kürzesten Weg von einer Position zu einer anderen, sondern bestimmt alle kürzesten Wege von jedem Punkt zu jedem anderen.

Der Graph darf negative Kanten enthalten, aber Vorraussetzung ist, dass keine negativen Kreise im Graph enthalten sind (d.h. Kreise die negative Kosten verursachen).

Algorithmus

Der Algorithmus basiert auf einer (Adjazenz-)Matrix. Die Knoten des Graphen werden als Index verwendet. Der Zeilenindex stellt den Startknoten dar, der Spaltenindex den Zielknoten.

T[1..n][1..n] of integer; //n = Anzahl der Knoten

//Initialisierung
Matrix mit Maximalwert initialisieren.
Hauptdiagonale mit 0 initialisieren

for i := 1 to n do
  for each Nachbar j von i do
     T[i][j] = Kosten(i nach j);

//Eigentliches Bestimmen der kürzesten Wege
for z := 1 to n do        //z = Zwischenknoten
  for i := 1 to n do      //i = Startknoten
    for j := 1 to n do    //j = Zielknoten
      if (T[i][z] + T[z][j]) < T[i][j]) then //"Wenn der Weg über den Zwischenknoten z besser ist
          T[i][j] := T[i][z] + T[z][j];      // als der direkte, nimm diesen Weg."

Falls auf der Hauptdiagonale irgendwann ein Wert kleiner 0 steht, dann hat man einen negativen Kreis gefunden. Dadurch ist nicht mehr sichergestellt, dass die Ergebnisse korrekt sind.

Am Ende des Algorithmus stehen in T[i][j] die minimalen Kosten, um von i nach j zu kommen. Steht in T[i][j] der Maximalwert (siehe Initialisierung), ist j von i aus nicht erreichbar.

Kritik

Vorteile:

• Der Algorithmus findet die minimalen Kosten von allen Wegen im Graph.
• Der Algorithmus ist deshalb besonders geeignet, um die kürzesten Wege in statischen Netzwerken zu finden, da er nur einmal ausgeführt werden muss.

Nachteile:

• Der Algorithmus muss bei Änderungen des Netzwerks erneut aufgerufgen werden und berechnet dann alles neu.
• Der Algorithmus benötigt O(n²) Speicherplatz.
• Mit einer Laufzeit von O(n³) ist er nicht besonders schnell.