Floyd-Warshall: Kürzeste Wege zwischen allen Knotenpaaren

Floyd-Warshall berechnet kürzeste Wege zwischen jedem Knotenpaar in einem gewichteten Graphen – auch in Graphen mit negativen Kantengewichten (aber nicht mit negativen Zyklen). Dijkstra von jeder Quelle auszuführen kostet O(V × (V+E) log V); Floyd-Warshall läuft unabhängig von der Kantendichte in O(V³). Für dichte Graphen mit V ≤ 500 ist Floyd-Warshall oft einfacher und ähnlich schnell.

Floyd-Warshalls zentrale Erkenntnis: dp[i][j][k] = kürzester Pfad von i nach j, der nur Knoten aus {0, 1, ..., k} als Zwischenknoten verwendet. Entweder verwendet der kürzeste Pfad den Knoten k als Zwischenknoten oder nicht. Falls ja: dp[i][j][k] = dp[i][k][k-1] + dp[k][j][k-1]. Falls nicht: dp[i][j][k] = dp[i][j][k-1]. Da die dritte Dimension nur vorwärts fortschreitet, kann sie eliminiert werden – wir aktualisieren direkt an Ort und Stelle.

Beginnen Sie mit einer V×V-Matrix: dist[i][i] = 0 (Entfernung eines Knotens zu sich selbst), dist[i][j] = weight für direkte Kanten und dist[i][j] = inf für Nichtkanten. Iterieren Sie dann über alle Zwischenknoten k und aktualisieren Sie die Paare (i, j). Die äußere Schleife über k muss zuerst kommen, damit wir Pfade über eine zunehmend größere Menge zulässiger Zwischenknoten korrekt aufbauen.

Verfolgen wir Floyd-Warshall an einem Graphen mit 4 Knoten. Nach der Verarbeitung jedes Zwischenknotens wird die Matrix um kürzere Pfade ergänzt, die über den Knoten k führen. Der Algorithmus verarbeitet mehrere Sprünge ganz natürlich, indem er kürzeste Pfade schrittweise aufbaut.

Überprüfen Sie nach der Ausführung von Floyd-Warshall die Hauptdiagonale: Wenn ein Wert dist[i][i] < 0 ist, gibt es einen negativen Zyklus, der durch den Knoten i verläuft. Das liegt daran, dass ein negativer Zyklus ermöglicht, i von i aus mit negativen Kosten zu erreichen. Wenn kein negativer Zyklus existiert, bleiben alle Diagonaleinträge 0.

Um den tatsächlichen Pfad von i nach j zu rekonstruieren, verwalten Sie eine next[i][j]-Matrix: Initialisieren Sie sie für direkte Kanten mit next[i][j] = j. Bei einer Aktualisierung über den Zwischenknoten k setzen Sie next[i][j] = next[i][k]. Um den Pfad wiederherzustellen, beginnen Sie bei i und folgen den next-Zeigern, bis j erreicht ist. Dies benötigt O(V²) Speicherplatz und O(V) für jede Pfadrekonstruktion.

Eine einfachere Variante: Die transitive Hülle beantwortet für alle Paare die Frage „Ist Knoten j von Knoten i aus erreichbar?“. Ersetzen Sie Distanzen durch boolesche Werte: reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j]). Dies ist Floyd-Warshall mit booleschem OR statt Addition und Minimum. Initialisieren Sie reach[i][i] = True und setzen Sie reach[i][j] = True für direkte Kanten.

Floyd-Warshall: O(V³) Zeit, O(V²) Speicherplatz. Für dichte Graphen (E ≈ V²) mit V ≤ 300 ist dieser Algorithmus schneller als Dijkstra V-mal auszuführen (in diesem Fall ebenfalls O(V³)). Für dünn besetzte Graphen mit V = 1000 und E = 3000 kosten V Dijkstra-Ausführungen O(V×E×log V) ≈ 33M, während Floyd-Warshall O(V³) = 10⁹ kostet – Dijkstra ist schneller. Wissen Sie, wann welcher Algorithmus geeignet ist.

Setzen Sie alle Kantengewichte auf 1 (oder verwenden Sie eine boolesche Adjazenzmatrix mit Floyd-Warshall, wobei Sie Addition statt Minimum verwenden): dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). Damit wird die minimale Anzahl von Hops zwischen allen Knotenpaaren berechnet – das Ergebnis einer BFS für alle Knotenpaare, aber in einem einzigen Floyd-Warshall-Durchlauf mit O(V³).

Floyd-Warshall kommt in Interviews bei Aufgaben vor, die Folgendes betreffen: (1) Distanzen zwischen allen Knoten eines kleinen Graphen, (2) das Ermitteln eines Zyklus mit einem negativen Gesamtgewicht, (3) die Berechnung kürzester Wege in Problemen zur Constraint-Propagation und (4) Aufgaben, die ausdrücklich Lösungen mit O(V³) verlangen, wobei V ≤ 200 gilt. Erwähnen Sie in einem Interview immer die Struktur mit drei Schleifen sowie die Voraussetzung, dass keine negativen Zyklen vorhanden sein dürfen, damit der Algorithmus korrekt ist.

Fügen Sie bei ungerichteten Graphen für jede Kante beide Richtungen hinzu: dist[u][v] = dist[v][u] = weight. Der Rest des Algorithmus bleibt identisch. Die resultierende Matrix ist symmetrisch: dist[i][j] == dist[j][i] für alle Knotenpaare. Achten Sie bei der Initialisierung darauf, nicht versehentlich gerichtete Kanten zuzuweisen – ungerichtete Kanten müssen vor Ausführung der drei Schleifen in beiden Richtungen zur Anfangsmatrix hinzugefügt werden.

Testen Sie Ihr Verständnis der Konzepte aus dieser Lektion im Bereich Data Structures & Algorithms — Coding Interview Prep.

In dieser Lektion haben Sie gelernt: Floyd-Warshall berechnet die kürzesten Wege zwischen allen Knotenpaaren mit drei verschachtelten Schleifen und der Rekurrenz dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]), negative Zyklen lassen sich erkennen, indem nach Abschluss geprüft wird, ob ein dist[i][i] < 0 ist, und der Algorithmus benötigt O(V³) Zeit und O(V²) Speicherplatz. Als Nächstes sehen wir uns Anwendungen kürzester Wege mit Network Delay Time sowie Techniken zur Pfadrekonstruktion an.