Algorithmus von Floyd und Warshall

Zweck und Grundidee

Der Algorithmus von Floyd und Warshall ist ein Algorithmus der Graphentheorie. In der Floyd-Version berechnet er die kürzesten Pfade und ihre Länge zwischen allen Paaren von Knoten eines Graphen (APSP, all-pairs shortest path). In der Warshall-Version berechnet er die transitive Hülle: Sie zeigt für jedes Knotenpaar, ob überhaupt ein Pfad vom ersten zum zweiten Knoten existiert.

Der Floyd-Warshall-Algorithmus arbeitet mit dynamischer Programmierung. Dabei werden Lösungen schrittweise aus bereits bekannten Teillösungen aufgebaut. Die zentrale Beobachtung lautet: Führt der kürzeste Weg von u nach v über w, dann sind auch die Teilpfade von u nach w und von w nach v jeweils minimal.

Berechnung der kürzesten Distanzen

Als Eingabe dient eine Gewichtsmatrix w. Der Eintrag w[i,j] ist das Gewicht der Kante von i nach j. Gibt es keine solche Kante, ist w[i,j] unendlich. Zunächst wird die Distanzmatrix d mit den Werten der Gewichtsmatrix initialisiert: d[i,j] = w[i,j].

Danach werden die Knoten mit k = 1 bis n nacheinander als mögliche Zwischenknoten zugelassen. Für jedes Paar i,j wird geprüft, ob der Weg über k kürzer ist als der bisher bekannte Weg:

d[i,j] = min(d[i,j], d[i,k] + d[k,j]).

Nach einem Durchlauf für k sind alle kürzesten Wege berücksichtigt, deren Zwischenknoten höchstens den Index k haben. Am Ende enthält d die kürzesten Distanzen für alle Knotenpaare.

Der Algorithmus funktioniert auch bei Kanten mit negativem Gewicht. Negative Zyklen führen jedoch zu falschen Ergebnissen und werden – anders als beim Bellman-Ford-Algorithmus – nicht direkt erkannt. Sie lassen sich an negativen Werten auf der Hauptdiagonalen der Distanzmatrix erkennen. Um numerische Probleme zu vermeiden, soll dies bereits jedes Mal geprüft werden, wenn beim Aktualisieren ein Diagonalelement geändert wird.

Transitive Hülle mit Warshall

Für die transitive Hülle wird statt einer Gewichtsmatrix eine Adjazenzmatrix verwendet. Dabei gilt w[i,j] = 1, wenn eine Kante von i nach j existiert, und w[i,j] = 0, wenn keine Kante existiert. Die Matrix d bedeutet dann: d[i,j] = 1 genau dann, wenn ein Pfad von i nach j existiert.

Warshalls Algorithmus betrachtet ebenfalls jeden Knoten k. Wenn d[i,k] = 1 und d[k,j] = 1 ist, wird d[i,j] auf 1 gesetzt. Damit wird festgehalten, dass ein Weg von i nach j über k vorhanden ist. In diesem Schritt existieren die Teilpfade von i nach k und von k nach j über Knoten mit Index kleiner als k.

Laufzeit und geeignete Alternativen

Die Laufzeit des Floyd-Warshall-Algorithmus beträgt O(n³), weil die drei Variablen k, i und j jeweils die Werte von 1 bis n durchlaufen; n ist die Anzahl der Knoten.

Er eignet sich besonders für dichte Graphen, also Graphen, in denen die meisten oder alle Knotenpaare durch Kanten verbunden sind, und wenn Pfade zwischen allen Knotenpaaren benötigt werden. Für dünne Graphen mit nicht-negativen Kantengewichten ist es besser, den Dijkstra-Algorithmus von jedem möglichen Startknoten auszuführen. Mit Fibonacci-Heaps hat wiederholtes Dijkstra die Laufzeit O(|E||V| + |V|² log |V|), die besser als O(|V|³) ist, wenn |E| deutlich kleiner als |V|² ist. Für dünne Graphen mit negativen Kanten, aber ohne negative Zyklen, kann der Algorithmus von Johnson mit derselben asymptotischen Laufzeit verwendet werden.

Algorithmen mit schneller Matrixmultiplikation können die Berechnung für dichte Graphen beschleunigen, benötigen aber typischerweise zusätzliche Annahmen über die Kantengewichte, etwa kleine ganze Zahlen. Wegen hoher konstanter Faktoren wären sie erst bei sehr großen Graphen schneller.

Ablauf an einem Graphen mit vier Knoten

Im Beispiel werden vier Knoten betrachtet. Zu Beginn bei k = 0 sind nur die einzelnen Kanten als Wege bekannt. Bei k = 1 wird etwa der Pfad [2,1,3] gefunden. Er ersetzt den kürzeren, aber gewichtsmäßig längeren Pfad [2,3]: Der Eintrag d[2,3] ändert sich von 3 zu d[2,1] + d[1,3] = 4 + (−2) = 2.

Bei k = 2 wird unter anderem der Pfad [4,2,1,3] aus den bereits bekannten Wegen [4,2] und [2,1,3] zusammengesetzt. Bei k = 3 werden alle Pfade berücksichtigt, die über die Knoten {1,2,3} führen. Bei k = 4 liegen schließlich alle kürzesten Pfade vor. Die endgültige Distanzmatrix ist:

Zeile 1: 0, −1, −2, 0 Zeile 2: 4, 0, 2, 4 Zeile 3: 5, 1, 0, 2 Zeile 4: 3, −1, 1, 0.

Die gezeigte C#-Implementierung speichert die Distanzen in einem zweidimensionalen Integer-Array. Nicht verbundene Knoten erhalten einen Schwellenwert auf Grundlage von int.MaxValue und werden bei der Ausgabe als „INF“ für unendlich dargestellt.