Floyd-Warshall Rechner

Pseudocode

Drei geschachtelte Schleifen und eine einzige Aktualisierungszeile. Die ganze Feinheit steckt in der Schleifenreihenfolge: k muss die äußerste Schleife sein, und das falsch zu machen ist der klassische Fehler.

FloydWarshall(graph):
    dist = V mal V Matrix, alles unendlich
    für jeden Knoten v:      dist[v][v] = 0
    für jede Kante (u,v,w):  dist[u][v] = w

    für k in Knoten:                // Zwischenknoten
        für i in Knoten:            // Quelle
            für j in Knoten:        // Ziel
                wenn dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
                    next[i][j] = next[i][k]   // Rekonstruktion

    // Negativer Zyklus genau dann, wenn dist[v][v] < 0

Die Invariante lautet: Nach dem Durchlauf für k ist dist[i][j] der kürzeste Weg von i nach j, der nur die ersten k Knoten als Zwischenstationen benutzt. Damit das gilt, muss k außen stehen: genau das erweitert die Menge erlaubter Zwischenstationen Schritt für Schritt. Steht k innen, terminiert der Algorithmus trotzdem und liefert plausible Zahlen, und genau das macht den Fehler so schwer auffindbar.

Durchgerechnetes Beispiel, Schritt für Schritt

Führe Floyd-Warshall auf einem kleinen gerichteten Graphen aus und beobachte, wie sich ein Eintrag zweimal verbessert, während die Menge der erlaubten Zwischenknoten wächst.

Beispielgraph: Gerichtete Kanten A nach B (3), A nach C (8), B nach C (2), B nach D (7) und C nach D (1).

1. Initialisieren. Nur direkte Kanten. Von A aus: B ist 3, C ist 8, D unerreichbar. Von B aus: C ist 2, D ist 7. Von C aus: D ist 1. Jeder Diagonaleintrag ist 0.
2. k = A. Nichts ändert sich. Keine Kante zeigt nach A, also ist dist[i][A] für jedes andere i unendlich und kein Weg kann über A laufen.
3. k = B. Zwei Verbesserungen. dist[A][C] sinkt von 8 auf dist[A][B] + dist[B][C] = 3 + 2 = 5. dist[A][D] fällt von unendlich auf 3 + 7 = 10, die erste endliche Route von A nach D.
4. k = C. Zwei weitere. dist[A][D] verbessert sich erneut, von 10 auf dist[A][C] + dist[C][D] = 5 + 1 = 6, und beachte, dass dabei der Wert von dist[A][C] benutzt wird, den der Durchlauf k = B gerade verbessert hat. dist[B][D] sinkt von 7 auf 2 + 1 = 3.
5. k = D. Nichts ändert sich, da D keine ausgehenden Kanten hat und nicht als Zwischenstation dienen kann.

Die Enddistanzen von A aus sind B 3, C 5, D 6. Der Eintrag A nach D verbesserte sich zweimal, von unendlich auf 10 und dann auf 6, was die Schichtung unmittelbar zeigt: der Durchlauf k = C konnte die bessere Route nur finden, weil der Durchlauf k = B bereits A nach C verbessert hatte. Diese Abhängigkeit ist der Grund, warum k die äußere Schleife sein muss.

Komplexität und woher sie kommt

Zeit: O(V^3) · Speicher: O(V^2)

Drei geschachtelte Schleifen über alle Knoten ergeben exakt V hoch 3 Iterationen mit jeweils konstantem Aufwand. Es gibt weder frühzeitigen Abbruch noch eine Abhängigkeit von der Kantenzahl, der Algorithmus kostet auf einem dünnen Graphen also dasselbe wie auf einem dichten. Der Speicher ist die V mal V Distanzmatrix, plus eine zweite Matrix, wenn du Wege und nicht nur ihre Längen rekonstruieren willst. In der Praxis ist V hoch 3 bis zu einigen tausend Knoten vertretbar; bei 5.000 sind es 125 Milliarden Operationen, und Dijkstra von jedem Knoten aus, mit O(V·E·log V), wird auf dünnen Graphen zur besseren Wahl.

Wann Floyd-Warshall-Algorithmus passt und wann nicht

Floyd-Warshall gewinnt bei Dichte und Einfachheit und verliert deutlich auf großen dünnen Graphen.

Häufige Fehler

• Die k-Schleife irgendwo außer ganz außen platzieren. Das ist der Fehler, der Floyd-Warshall auszeichnet. Steht k innen, bricht die Invariante und das Ergebnis ist für manche Paare stillschweigend zu groß. Es entsteht keine Fehlermeldung und alles wirkt plausibel, sodass der Fehler flüchtige Tests übersteht. Die Reihenfolge muss k, dann i, dann j lauten.
• Zu unendlich addieren. Wird unendlich als große ganze Zahl dargestellt, läuft dist[i][k] + dist[k][j] über und wird negativ, wodurch kürzeste Wege entstehen, die es nicht gibt. Sichere die Addition ab oder nutze einen Platzhalter, der klein genug ist, dass seine Verdopplung nicht überläuft.
• Ihn ungeprüft auf einem Graphen mit negativem Zyklus ausführen. Der Algorithmus versagt nicht, er liefert einfach sinnlose Werte. Nach den Schleifen liegt jeder Knoten mit dist[v][v] unter null auf einem negativen Zyklus. Prüfe das, bevor du der Matrix vertraust.
• Ihn auf einem großen dünnen Graphen verwenden. V hoch 3 ignoriert E vollständig. Auf einem Graphen mit 10.000 Knoten und 30.000 Kanten führt Floyd-Warshall eine Billion Operationen aus, während Dijkstra von jedem Knoten aus einige hundert Millionen benötigt.
• Die Diagonale nicht initialisieren. dist[v][v] muss bei 0 beginnen, nicht bei unendlich. Bleibt sie unendlich, brechen bereits die allerersten Relaxationen und alles Folgende wird stillschweigend verfälscht.

Häufig gestellte Fragen

Wofür wird der Floyd-Warshall-Algorithmus verwendet?

Er berechnet in einem einzigen Lauf die kürzesten Wege zwischen allen Knotenpaaren eines gewichteten Graphen. Er dient Distanztabellen für alle Paare in der Routenplanung, der transitiven Hülle einer Relation, der Bestimmung des Graphdurchmessers, der Arbitrageerkennung über alle Währungspaare zugleich und allgemein Situationen, in denen viele verschiedene Quell-Ziel-Paare abgefragt werden.

Wie ist die Zeitkomplexität von Floyd-Warshall?

O(V hoch 3) Zeit und O(V hoch 2) Speicher, ohne jede Abhängigkeit von der Kantenzahl. Drei geschachtelte Schleifen laufen über alle Knoten mit konstantem Aufwand im Inneren, und es gibt keinen vorzeitigen Abbruch. Das macht ihn unempfindlich gegenüber der Dichte, was auf dichten Graphen ein Vorteil und auf dünnen ein erheblicher Nachteil ist.

Warum muss k die äußerste Schleife sein?

Weil k die Menge der als Zwischenstationen erlaubten Knoten darstellt und der Algorithmus diese Menge Knoten für Knoten erweitert. Nach dem Durchlauf für ein bestimmtes k ist jeder Eintrag korrekt, sofern nur die ersten k Knoten als Zwischenstationen dienen. Steht k nicht außen, gilt diese Invariante nie, und der Algorithmus liefert ohne jede Fehlermeldung zu große Distanzen.

Kann Floyd-Warshall negative Gewichte verarbeiten?

Ja, negative Kanten sind unproblematisch, solange es keinen negativen Zyklus gibt. Nach dem Durchlauf bedeutet ein negativer Wert auf der Diagonalen, also dist[v][v] unter null, dass v auf einem negativen Zyklus liegt und die Distanzen mit v sinnlos sind.

Wann sollte ich Dijkstra statt Floyd-Warshall verwenden?

Wenn der Graph dünn ist und die Gewichte nichtnegativ sind. Dijkstra von jedem Knoten aus kostet O(V·E·log V), was auf einem Graphen mit weit weniger als V hoch 2 Kanten drastisch schneller ist als V hoch 3. Floyd-Warshall gewinnt auf dichten Graphen, auf kleinen Graphen und wenn du die kürzestmögliche Implementierung willst.