Der Floyd-Warshall-Algorithmus erklärt

Mohammed Islam Hadjoudj

Experte für Operations Research

1. Einführung in den Floyd-Warshall-Algorithmus

Der Floyd-Warshall-Algorithmus löst das Problem der kürzesten Wege zwischen allen Knotenpaaren. Für einen gewichteten, gerichteten Graphen bestimmt er die kürzeste Distanz zwischen jedem Knotenpaar, nicht nur die Distanzen von einem gewählten Startknoten aus. Am Ende halten Sie eine vollständige Distanzmatrix in der Hand: Schlagen Sie einen beliebigen Start und ein beliebiges Ziel nach, und die Antwort steht bereits dort.

Das ist eine andere Frage als die, die der Dijkstra-Algorithmus und der Bellman-Ford-Algorithmus beantworten. Jene sind Einzelquellen-Algorithmen: Sie geben einen Startknoten vor, und sie sagen Ihnen, wie weit jeder andere Knoten davon entfernt ist. Floyd-Warshall beantwortet all diese Fragen auf einmal, für jeden möglichen Startknoten, in einem einzigen Durchlauf.

Bemerkenswert ist, wie wenig der Algorithmus dafür benötigt. Es gibt keine Prioritätswarteschlange, keine Besuchsmenge und keine Rekursion. Der gesamte Algorithmus besteht aus drei verschachtelten Schleifen über eine Matrix, und seine Korrektheit beruht auf einer einzigen klaren Idee aus der dynamischen Programmierung. Er verarbeitet zudem negative Kantengewichte, was Dijkstra nicht kann, und meldet das Vorhandensein eines negativen Zyklus als Nebenprodukt der Arbeit, die er ohnehin leistet.

2. Alle Paare oder eine Quelle: Warum nicht einfach Dijkstra wiederholen?

Ein naheliegender Einwand lautet, man könne einfach einen Einzelquellen-Algorithmus von jedem Knoten aus einmal ausführen. Dieser Ansatz ist legitim und manchmal vorzuziehen, daher lohnt sich eine genaue Betrachtung, wann welcher gewinnt.

Den Dijkstra-Algorithmus von allen V Knoten aus auszuführen kostet mit einem binären Heap O(V * E log V). In einem dünn besetzten Graphen, in dem die Kantenzahl E nahe bei V liegt, entspricht das ungefähr O(V2 log V) und schlägt Floyd-Warshall deutlich. In einem dicht besetzten Graphen, in dem E sich V2 nähert, kostet dieselbe Wiederholung etwa O(V3 log V), und die konstante Schranke O(V3) von Floyd-Warshall ist die bessere.

Zwei weitere Überlegungen entscheiden die Wahl oft, noch bevor die Komplexität ins Spiel kommt:

• Negative Gewichte. Wiederholtes Dijkstra ist schlicht falsch, sobald eine Kante negativ ist. Sie müssten Bellman-Ford einsetzen, insgesamt O(V2 * E), oder den Graphen zuvor mit dem Johnson-Algorithmus umgewichten. Floyd-Warshall akzeptiert negative Kanten direkt.
• Einfachheit. Floyd-Warshall umfasst etwa fünf Codezeilen ohne begleitende Datenstrukturen. Bei den kleinen, dicht besetzten Graphen, die in Ablaufplanung, Routing-Tabellen und Wettbewerbsprogrammierung üblich sind, ist diese Verlässlichkeit mehr wert als ein asymptotischer Vorsprung.

3. Die Kernidee: Zwischenknoten

Der Einfall hinter Floyd-Warshall besteht darin, das Problem so einzuschränken, dass es sich leicht ausbauen lässt. Statt sofort zu fragen "Was ist der kürzeste Weg von i nach j?", stellt er eine engere Frage:

Was ist der kürzeste Weg von i nach j, der als Zwischenstationen nur die Knoten einer bestimmten erlaubten Menge benutzen darf?

Nummerieren Sie die Knoten von 1 bis V. Definieren Sie die erlaubte Menge als die ersten k Knoten und schreiben Sie dk(i, j) für die kürzeste Distanz von i nach j, die nur {1, 2, ..., k} als Zwischenknoten verwendet. Die Endpunkte i und j sind stets erlaubt, unabhängig davon, ob sie in der erlaubten Menge liegen. Eingeschränkt sind nur die Knoten strikt dazwischen.

Die beiden Enden dieser Definition sind aufschlussreich. Bei k = 0 darf nichts als Zwischenstation dienen, also ist d0(i, j) genau das Gewicht der direkten Kante von i nach j oder unendlich, falls es keine solche Kante gibt. Bei k = V ist jeder Knoten erlaubt, also ist dV(i, j) die wahre, uneingeschränkte kürzeste Distanz. Der Algorithmus ist die Maschinerie, die vom ersten Fall zum zweiten führt.

4. Die Rekursionsgleichung

Angenommen, Sie kennen bereits alle Werte von dk-1 und möchten dk bestimmen. Betrachten Sie den kürzesten Weg von i nach j, der {1, ..., k} benutzen darf. Es gibt genau zwei Möglichkeiten, und sie schließen einander aus:

1. Der Weg benutzt Knoten k nicht. Dann benutzt er nur {1, ..., k-1}, seine Länge ist also dk-1(i, j), ein Wert, den Sie bereits haben.
2. Der Weg benutzt Knoten k. Da ein kürzester Weg keinen Knoten wiederholt, führt er genau einmal durch k. Das teilt ihn in einen Abschnitt von i nach k und einen von k nach j, und keiner der beiden darf k als Zwischenstation verwenden. Seine Länge ist also dk-1(i, k) + dk-1(k, j), und beide Terme sind ebenfalls bereits bekannt.

Der kürzeste Weg ist der kleinere der beiden, woraus sich die Rekursion im Herzen des Algorithmus ergibt:

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

In Worten: Der Umweg über k lohnt sich nur, wenn der Abstecher nach k und weiter nach j kürzer ist als die beste ohne ihn gefundene Route. Das ist dynamische Programmierung in Reinform. Jedes Teilproblem wird einmal gelöst, gespeichert und wiederverwendet.

In der Praxis speichert niemand V getrennte Matrizen. Die Werte lassen sich in einer einzigen V x V-Matrix an Ort und Stelle aktualisieren, denn während der Iteration k können sich die Einträge d(i, k) und d(k, j) nicht ändern: Eine Aktualisierung würde d(k, k) erfordern, und das ist 0, solange der Graph keinen negativen Zyklus enthält. Einen bereits in derselben Runde überschriebenen Wert zu lesen ist daher unschädlich, und der Speicherbedarf sinkt von O(V3) auf O(V2).

5. Schritt für Schritt durchgerechnet

Abstrakte Rekursionen werden klar, sobald man sie mit Zahlen durchspielt. Nehmen wir einen gerichteten Graphen mit vier Knoten und diesen Kanten:

• 1 -> 2 mit Gewicht 5
• 1 -> 4 mit Gewicht 10
• 2 -> 3 mit Gewicht 3
• 3 -> 4 mit Gewicht 1

Initialisieren Sie die Matrix allein aus den Kanten. Die Diagonale ist 0, weil jeder Knoten sich selbst ohne Kosten erreicht, und jede fehlende Kante ist unendlich.

k = 0 (nur direkte Kanten)

        1     2     3     4
  1     0     5     inf   10
  2     inf   0     3     inf
  3     inf   inf   0     1
  4     inf   inf   inf   0

Runde k = 1. Knoten 1 ist nun als Zwischenstation zugelassen. Jede Aktualisierung bräuchte ein endliches d(i, 1), doch Spalte 1 ist überall außer auf der Diagonale unendlich, denn keine Kante führt zu Knoten 1. Nichts ändert sich.

Runde k = 2. Knoten 2 wird verfügbar. Zeile 2 liefert ein endliches d(2, 3) = 3, Spalte 2 ein endliches d(1, 2) = 5. Daraus ergibt sich eine mögliche Verbesserung:

• d(1, 3) war unendlich. Über Knoten 2 wird daraus 5 + 3 = 8. Aktualisiert auf 8.

Runde k = 3. Knoten 3 wird verfügbar, und d(3, 4) = 1. Zwei Einträge verbessern sich:

• d(1, 4) war 10 über die direkte Kante. Über Knoten 3 wird daraus d(1, 3) + d(3, 4) = 8 + 1 = 9. Aktualisiert auf 9.
• d(2, 4) war unendlich. Über Knoten 3 wird daraus 3 + 1 = 4. Aktualisiert auf 4.

Beachten Sie, dass die Verbesserung von d(1, 4) auf d(1, 3) = 8 beruhte, einem Wert aus der vorigen Runde. Der Algorithmus baut längere Wege aus kürzeren, die er bereits bewiesen hat.

Runde k = 4. Knoten 4 hat keine ausgehenden Kanten, Zeile 4 ist also außer auf der Diagonale unendlich, und kein Weg kann sinnvoll durch ihn führen. Nichts ändert sich, und der Algorithmus endet.

Ergebnis (alle Paare)

        1     2     3     4
  1     0     5     8     9
  2     inf   0     3     4
  3     inf   inf   0     1
  4     inf   inf   inf   0

Die Antwort für 1 -> 4 lautet 9, über die Route 1 -> 2 -> 3 -> 4 zu Kosten von 5 + 3 + 1, was die direkte Kante mit Gewicht 10 schlägt. Die verbleibenden Unendlichkeiten sind korrekt und nicht etwa unfertig: Keine Kante führt zu Knoten 1, also kann ihn nichts erreichen.

6. Implementierung und Pseudocode

Der Algorithmus ist kurz genug, um ihn auswendig zu lernen. Das eine Detail, auf das es mehr ankommt als auf jedes andere, ist die Schleifenreihenfolge.

function FloydWarshall(W, V):
    // W[i][j] = Gewicht der Kante i -> j, sonst Infinity
    // dist ist eine V x V Matrix

    for i from 1 to V:
        for j from 1 to V:
            dist[i][j] = W[i][j]
        dist[i][i] = 0

    // k MUSS die äußerste Schleife sein
    for k from 1 to V:
        for i from 1 to V:
            for j from 1 to V:
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

    return dist

k muss die äußerste Schleife sein. Das ist die mit Abstand häufigste Art, den Algorithmus falsch zu schreiben. Die Rekursion verlangt, dass jedes Paar (i, j) bezüglich des Zwischenknotens k aktualisiert wird, bevor zu k + 1 übergegangen wird. Steht k innen, wird die Matrix in einer Reihenfolge gefüllt, die keine Bedeutung hat, und das Ergebnis sind Distanzen, die plausibel aussehen, aber nicht optimal sind.

Ein Hinweis zur Implementierung: Wenn Sie Unendlich durch einen großen Platzhalter wie INT_MAX statt durch eine echte Gleitkomma-Unendlichkeit darstellen, kann dist[i][k] + dist[k][j] überlaufen und zu einer negativen Zahl umschlagen, die der Vergleich dann bereitwillig akzeptiert. Verwenden Sie entweder ein echtes Unendlich oder sichern Sie die Addition ab, indem Sie die Aktualisierung überspringen, sobald einer der Operanden der Platzhalter ist.

7. Zeit- und Speicherkomplexität

• Zeit: O(V3). Drei verschachtelte Schleifen laufen je V mal, und der Rumpf besteht aus einem einzigen Vergleich und einer Zuweisung. Es gibt keinen nennenswerten besten oder schlechtesten Fall: Der Algorithmus führt bei jeder Eingabe exakt V3 Relaxationstests durch, unabhängig davon, wie viele Kanten der Graph tatsächlich hat.
• Speicher: O(V2). Eine Distanzmatrix, an Ort und Stelle aktualisiert. Eine zweite Matrix gleicher Größe wird benötigt, wenn Sie zusätzlich Wege rekonstruieren möchten.

Die Unempfindlichkeit gegenüber E ist das prägende Merkmal. Ein Graph mit vier Knoten und drei Kanten kostet genauso viel wie einer mit vier Knoten und zwölf. Das ist bei dünn besetzten Graphen verschwenderisch und bei dichten vollkommen effizient. Im Gegenzug ist der konstante Faktor sehr klein und das Speicherzugriffsmuster regelmäßig und cache-freundlich, sodass Floyd-Warshall bei Graphen mit einigen hundert Knoten seine Asymptotik oft übertrifft.

8. Negative Kanten und Erkennung negativer Zyklen

Floyd-Warshall akzeptiert negative Kantengewichte ohne Anpassung. Die Rekursion setzt nie voraus, dass das Verlängern eines Weges seine Länge erhöht, und genau diese Annahme lässt den Dijkstra-Algorithmus bei negativen Eingaben scheitern.

Negative Zyklen sind eine andere Sache, und kein Algorithmus kann in ihrer Gegenwart sinnvolle kürzeste Distanzen liefern: Man kann den Zyklus beliebig oft umrunden und die Kosten unbegrenzt drücken. Floyd-Warshall bietet Ihnen jedoch eine Möglichkeit, das kostenlos zu bemerken. Prüfen Sie nach Ende des Algorithmus die Diagonale:

for i from 1 to V:
    if dist[i][i] < 0:
        melde "negativer Zyklus erkannt"

Die Diagonale wurde mit 0 initialisiert. Ein Knoten kann nur dann eine negative Distanz zu sich selbst erhalten, wenn es einen geschlossenen Weg gibt, der bei ihm beginnt und endet und dessen Gesamtgewicht unter null liegt, und genau das ist die Definition eines negativen Zyklus. Wo Bellman-Ford einen eigenen zusätzlichen Durchlauf über alle Kanten braucht, um dasselbe festzustellen, genügt Floyd-Warshall ein Blick auf V bereits berechnete Einträge.

Beachten Sie die Reichweite der Prüfung. Sie meldet jeden negativen Zyklus, an dem der betreffende Knoten beteiligt ist. Ist die Diagonale sauber, ist jede Distanz in der Matrix vertrauenswürdig. Ist sie es nicht, sollten die endlichen Werte an anderer Stelle als bedeutungslos gelten und nicht bloß als ungenau.

9. Die tatsächlichen Wege rekonstruieren

Die Distanzmatrix hält fest, wie weit zwei Knoten voneinander entfernt sind, aber nicht, welche Route das erreicht. Die Route zurückzugewinnen erfordert eine zusätzliche Matrix, und das günstigste Verfahren speichert für jedes Paar den nächsten Knoten auf dem Weg.

Initialisieren Sie next[i][j] = j, wann immer eine direkte Kante existiert, und lassen Sie den Eintrag sonst leer. Sobald die Hauptschleife dist[i][j] über k verbessert, übernehmen Sie den ersten Schritt der neuen Route:

if dist[i][k] + dist[k][j] < dist[i][j]:
    dist[i][j] = dist[i][k] + dist[k][j]
    next[i][j] = next[i][k]

Die Zuweisung lautet next[i][k], nicht k. Der erste Zug auf der verbesserten Reise von i nach j ist der erste Zug der Reise von i nach k, und das kann durchaus ein ganz anderer Knoten sein. Den Weg auszulesen ist dann ein kurzer Spaziergang: bei i beginnen, wiederholt next folgen und bei j anhalten. Das kostet O(V2) zusätzlichen Speicher und praktisch keine zusätzliche Zeit.

10. Varianten und Anwendungen in der Praxis

Die Struktur aus drei Schleifen lässt sich weit über kürzeste Wege hinaus verallgemeinern, denn die Rekursion benötigt nur eine Operation, die zwei Abschnitte verknüpft, und eine, die zwischen Alternativen wählt.

Transitive Hülle (Warshall-Algorithmus)

Ersetzen Sie die Addition durch das logische UND und das Minimum durch das logische ODER, und dieselben Schleifen berechnen die Erreichbarkeit: ob überhaupt ein Weg zwischen zwei Knoten existiert, unabhängig von den Kosten. Das ist Warshalls ursprüngliches Ergebnis von 1962 und der Grund, warum der kombinierte Algorithmus beide Namen trägt. Es findet sich in der Datenflussanalyse von Compilern, in der Abhängigkeitsauflösung und in der Anfrageplanung von Datenbanken.

Breiteste Wege und Engpassprobleme

Ersetzen Sie die Addition durch das Minimum und das Minimum durch das Maximum, und der Algorithmus findet die Route, deren engste Verbindung so breit wie möglich ist. Das ist die natürliche Formulierung für Routing mit maximaler Bandbreite in einem Netzwerk und für Kapazitätsplanung in der Logistik.

Netzwerk-Routing und Latenzmatrizen

Netzbetreiber benötigen häufig eine vollständige Matrix der Latenzen oder Hop-Zahlen zwischen allen Knotenpaaren einer Topologie. Backbone-Topologien sind meist dicht und von überschaubarer Knotenzahl, und genau dafür wurde Floyd-Warshall geschaffen.

Währungsarbitrage

Modellieren Sie Währungen als Knoten und Wechselkurse als Kanten. Der negative Logarithmus jedes Kurses verwandelt die Multiplikation von Kursen in die Addition von Gewichten, und eine profitable Arbitrageschleife wird zu einem negativen Zyklus. Die Diagonalprüfung meldet dann, ob eine Arbitragemöglichkeit besteht, und die next-Matrix rekonstruiert die Abfolge der Geschäfte.

11. Wissenschaftliche Quellen und Geschichte

Die Zuschreibung des Algorithmus ist ungewöhnlich verworren. Mehrere Forscher gelangten innerhalb weniger Jahre unabhängig voneinander zu denselben drei Schleifen.

• Stephen Kleene (1956) beschrieb das zugrunde liegende Verfahren bei der Umwandlung endlicher Automaten in reguläre Ausdrücke, was strukturell dieselbe Hüllenberechnung ist.
• Bernard Roy (1959) veröffentlichte den Algorithmus in im Wesentlichen moderner Form in Transitivite et connexite, drei Jahre vor den Arbeiten, die ihm seinen geläufigen Namen gaben.
• Stephen Warshall (1962) veröffentlichte die Variante für die transitive Hülle und bewies den nach ihm benannten Satz über Boolesche Matrizen.
• Robert W. Floyd (1962) veröffentlichte die Variante für kürzeste Wege als bemerkenswert knappe Notiz, Algorithm 97: Shortest Path, in Communications of the ACM.
• Peter Ingerman (1962) beschrieb die heute übliche Formulierung mit drei verschachtelten Schleifen noch im selben Jahr in derselben Zeitschrift.

Für eine strenge Darstellung mit vollständigen Korrektheitsbeweisen ist Cormen, Leiserson, Rivest und Stein, Introduction to Algorithms, im Kapitel über kürzeste Wege zwischen allen Knotenpaaren das Standardwerk. Wer Ansätze für dünn besetzte Graphen vergleicht, sollte zusätzlich den Johnson-Algorithmus studieren, der einen Graphen so umgewichtet, dass wiederholtes Dijkstra auch bei negativen Kanten gültig bleibt. Die vollständigen Quellenangaben finden sich am Ende dieses Artikels.