Floyd-Warshall-Algorithmus

Nach dem Schritt für Zwischenknoten k enthält D_ij den besten Weg von i nach j, dessen innere Knoten aus der bisher zugelassenen Menge stammen. Die Aktualisierung vergleicht den alten Weg mit einer Route über k: D_ik+D_kj. Jeder betrachtete Weg vermeidet k oder zerfällt bei Nutzung von k in zwei Teilwege. Diese Zerlegung ist die dynamische Programmieridee des Verfahrens und erklärt, weshalb die Distanzwerte entlang gerichteter Kanten addiert werden. Bei ungerichteten Graphen wird jede Kante als zwei entgegengesetzte gerichtete Einträge in der Anfangsmatrix repräsentiert.

Die übliche In-place-Implementierung führt k als äußere Schleife, damit jede Stufe des dynamischen Programms vollständig abgeschlossen wird, bevor der nächste Zwischenknoten erlaubt ist. Wird i oder j nach außen gezogen, können aktualisierte Werte in einer Reihenfolge wiederverwendet werden, die nicht mehr zum Stufeninvariant passt. Die scheinbar gleiche Rekurrenz liefert dann nicht zwingend dieselben korrekten Werte. Die Schleifenordnung ist somit Teil der Implementierung, nicht bloß eine Stilfrage. Die Schleifeninvariante beschreibt genau, welche Zwischenknoten nach einer vollständigen k-Stufe bereits zugelassen wurden. Der Wert von k kodiert somit den aktuellen Wissensstand des dynamischen Programms.

Floyd–Warshall kann negative Kantengewichte verarbeiten, im Unterschied zu Dijkstra. Es darf aber keinen negativen Zyklus geben, der für betrachtete Wege beliebig oft durchlaufen werden kann; dann wäre ein kürzester Weg nach unten unbeschränkt. Nach dem Algorithmus weist ein negatives Diagonalelement D_ii auf einen erreichbaren negativen Zyklus hin. Betroffene Paare müssen entsprechend markiert werden, statt ihnen eine gewöhnliche endliche kürzeste Distanz zuzuschreiben. Zur Erkennung eines Zyklus reicht ein negatives Diagonalelement; seine Auswirkungen müssen anschließend auf erreichbare Paare übertragen werden. Für endliche kürzeste Wege muss die Zyklusbedingung im gesamten relevanten Teilgraphen gelten.

Es gibt V mögliche Zwischenknoten und zu jedem k werden alle V² geordneten Paare (i,j) untersucht. Daraus folgen Θ(V³) Rechenzeit. Gespeichert wird eine V-mal-V-Distanzmatrix mit Θ(V²) Speicherbedarf. Das Verfahren ist daher für mittelgroße oder dichte Graphen oft übersichtlich. Bei großen dünn besetzten Graphen können wiederholte Einquellenverfahren günstiger sein, abhängig von Graphstruktur, Gewichten und Zahl der angefragten Startpunkte. Der Speicherbedarf kann für sehr große Graphen den Einsatz einer dünneren Repräsentation oder anderer Algorithmen nahelegen. Die asymptotischen Kosten ergeben sich direkt aus den drei verschachtelten Schleifen.

Am Anfang beträgt die direkte Distanz von A nach C fünf. Sobald B als Zwischenknoten erlaubt ist, kostet der Weg A→B→C insgesamt 3+(−1)=2. Der Algorithmus setzt deshalb D_AC=min(5,2)=2. Die Rechnung nutzt das negative Kantengewicht korrekt; sie bleibt sinnvoll, solange kein negativer Zyklus existiert. Man kann das Ergebnis unmittelbar prüfen, indem man beide verfügbaren Routen vergleicht und ihre Kantengewichte addiert. Ein negativer Kanteneintrag allein erzeugt keinen Zyklus; erst eine Rückverbindung kann die Summe beliebig oft senken. Die Initialisierung setzt außerdem D_ii=0 und nutzt unendlich für nicht vorhandene direkte Kanten.