Der Floyd–Warshall-Algorithmus

Alte Straßenatlanten hatten hinten eine Tabelle: die Entfernung zwischen je zwei Städten. Floyd–Warshall berechnet eine solche Tabelle, und er ist einer der kürzesten Algorithmen überhaupt: drei Schleifen, ein Vergleich, und jeder kürzeste Abstand fällt an seinen Platz.

Ein kleiner Graph, dessen Kanten Längen haben, neben einer Tabelle der Abstände zwischen allen Knotenpaaren, mit einer hervorgehobenen Zeile und Spalte
Ein kleiner Graph, dessen Kanten Längen haben, neben einer Tabelle der Abstände zwischen allen Knotenpaaren, mit einer hervorgehobenen Zeile und Spalte

Die Idee

Der Dijkstra-Algorithmus und Bellman–Ford finden die kürzesten Abstände von einem Start aus. Floyd–Warshall findet sie von jedem Knoten zu jedem anderen auf einmal, in einer Tabelle mit einer Zeile und einer Spalte pro Knoten. Er beginnt mit dem, was die Kanten direkt sagen, und verbessert dann die ganze Tabelle, indem er immer mehr Knoten als Zwischenhalte auf dem Weg erlaubt.

Schritt für Schritt

Füllen Sie die Tabelle: 0 von jedem Knoten zu sich selbst, die Länge der Kante zwischen Nachbarn und sonst unendlich. Dann für jeden Knoten k und jedes Paar i, j: Ist der Abstand von i nach k plus der Abstand von k nach j kleiner als der Abstand von i nach j, tragen Sie die kleinere Zahl ein. Das ist der ganze Algorithmus. Im Code sind es drei Schleifen, mit k außen.

Ein Beispiel

Nehmen Sie vier Knoten mit den Kanten A–B der Länge 3, B–C 1, A–C 5 und C–D 2. Die Tabelle beginnt mit diesen Werten und mit unendlich für A–D und B–D. Runde A ändert nichts, denn jeder Weg über A ist länger. Runde B findet A nach C über B: 3 + 1 = 4, kürzer als 5. Runde C findet A nach D über C: 4 + 2 = 6, und B nach D: 1 + 2 = 3, beides die ersten gefundenen Wege. Runde D ändert nichts. Die fertige Tabelle: A–B 3, A–C 4, A–D 6, B–C 1, B–D 3, C–D 2.

Warum die Reihenfolge der Schleifen zählt

Der Zwischenhalt k muss die äußere Schleife sein. Nach der Runde für k ist jeder Eintrag der kürzeste Abstand, der nur die ersten k Knoten als Zwischenhalte nutzt, und die nächste Runde baut darauf auf: Ein bester Weg über den neuen Zwischenhalt ist ein bester Weg zu ihm plus ein bester Weg von ihm, beide schon richtig. Steht k in einer inneren Schleife, geht diese Garantie verloren, und es können falsche Abstände bleiben. Die Tabelle während einer Runde direkt zu überschreiben ist sicher, denn Zeile und Spalte von k selbst ändern sich in dieser Runde nicht.

Geschichte und Anwendungen

Bernard Roy beschrieb das Verfahren 1959. 1962 veröffentlichte Stephen Warshall es für die transitive Hülle, die nur fragt, ob ein Knoten einen anderen erreichen kann, und Robert Floyd für kürzeste Wege. Es berechnet Entfernungstabellen und Routingtabellen, findet den Durchmesser eines Netzes, zeigt, welche Knoten welche erreichen, und verrät mit einem negativen Eintrag auf der Diagonale einen negativen Zyklus.

Selbst ausprobieren

Öffnen Sie die App und drücken Sie Schritt. Auf einer Seite ist der Graph, auf der anderen die Tabelle. Jede Runde hebt Zeile und Spalte des aktuellen Zwischenhalts hervor; jeder Schritt trägt den kürzeren Abstand eines Paares ein und umrandet die beiden Einträge, die addiert wurden. Zellen, die sich in dieser Runde geändert haben, sind getönt. Wählen Sie Start und Ziel, um den kürzesten Weg zwischen beiden zu sehen, wenn die Tabelle fertig ist.

Häufig gestellte Fragen

Welche Zeitkomplexität hat Floyd–Warshall?

O(n³) bei n Knoten, egal wie viele Kanten es gibt, und O(n²) Speicher für die Tabelle. Für kleine oder dichte Graphen ist er das Mittel der Wahl, denn dort läuft seine einfache Schleife sehr schnell.

Floyd–Warshall oder Dijkstra von jedem Knoten aus?

Für einen dichten Graphen oder wenn Kanten negativ sein können, ist Floyd–Warshall einfacher und etwa gleich schnell. Für einen großen, dünn besetzten Graphen mit nicht negativen Kanten ist es schneller, den Dijkstra-Algorithmus von jedem Knoten aus laufen zu lassen.

Ist Floyd–Warshall dynamische Programmierung?

Ja. Er löst die Aufgabe für Wege mit Zwischenhalten unter den ersten k Knoten mithilfe der Antworten für die ersten k − 1 Knoten und führt dabei nur eine Tabelle, die er laufend überschreibt.

Was ist die transitive Hülle?

Die Tabelle, welche Knoten welche erreichen können, ohne Abstände. Warshalls Version des Algorithmus berechnet sie mit „oder“ und „und“ statt „min“ und „+“.

Bereit, es auszuprobieren?

Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.

Floyd–Warshall ausprobieren