Zwischenhalt
Verkürzte Paare
Geprüfte Paare

  • Aktueller Zwischenhalt
  • Schon Zwischenhalt
  • Verkürztes Paar
  • Weg
Ein Klick auf einen Knoten setzt

Mehr zum Floyd–Warshall-Algorithmus

Floyd–Warshall-Algorithmus

Wie weit ist es von jeder Stadt zu jeder anderen? Floyd–Warshall beantwortet das in einem Zug, mit einer Tabelle und drei verschachtelten Schleifen. Jede Runde erlaubt einen weiteren Knoten als Zwischenhalt und fragt für jedes Paar, ob der Umweg über ihn kürzer ist. Gehen Sie Schritt für Schritt vor, um zu sehen, wie sich die Tabelle füllt und die Abstände sinken. Drücken Sie Abspielen, um zuzusehen, wie sich die Tabelle füllt, oder Schritt und Zurück, um Schritt für Schritt vorzugehen. Ziehen Sie den Schrittregler, um an eine beliebige Stelle zu springen. Die Tabelle enthält den kürzesten bisher gefundenen Abstand zwischen jedem Paar von Knoten; die Zahl auf jeder Kante ist ihre Länge. Jede Runde erlaubt einen weiteren Knoten als Zwischenhalt auf dem Weg, und jeder Schritt zeigt ein Paar, das über ihn kürzer wird. Klicken Sie auf einen Knoten, um ihn zum Start zu machen; stellen Sie den Klick auf Ziel um und klicken Sie auf einen anderen Knoten, um am Ende den kürzesten Weg zwischen beiden zu sehen. Neuer Graph erzeugt einen anderen Graphen; wählen Sie, wie viele Knoten und Kanten er hat. Wenn das Feld ausgewählt ist, gehen die Pfeiltasten schrittweise vor, die Leertaste startet und pausiert, und Pos1 und Ende springen zum Anfang und zum Ende.

Wie es funktioniert

  1. Drücken Sie Abspielen, oder gehen Sie mit Schritt und Zurück schrittweise vor. Ziehen Sie den Schrittregler, um an eine beliebige Stelle zu springen.
  2. Beobachten Sie die Tabelle: Zeile und Spalte des aktuellen Zwischenhalts sind getönt, und jeder Schritt trägt einen kürzeren Abstand ein.
  3. Wählen Sie Start und Ziel, um am Ende den kürzesten Weg zwischen beiden zu sehen. Neuer Graph erzeugt einen anderen Graphen zum Ausprobieren.

So funktioniert Floyd–Warshall

Legen Sie eine Tabelle mit einer Zeile und einer Spalte pro Knoten an. Tragen Sie 0 auf der Diagonale ein, die Länge der Kante, wo zwei Knoten verbunden sind, und sonst überall unendlich. Nehmen Sie dann jeden Knoten k der Reihe nach als möglichen Zwischenhalt. Vergleichen Sie für jedes Paar i, j den Abstand von i nach j in der Tabelle mit dem Abstand von i nach k plus dem Abstand von k nach j, und behalten Sie den kleineren. Nach dem letzten Knoten ist jeder Eintrag der kürzeste Abstand zwischen seinen beiden Knoten.

Warum es funktioniert

Nach der Runde für k enthält die Tabelle für jedes Paar den kürzesten Weg, dessen Zwischenhalte alle unter den bisher bearbeiteten Knoten sind. Die Runde für den nächsten Knoten muss nur entscheiden, ob dieser Knoten hilft: Ein kürzester Weg über ihn ist ein kürzester Weg zu ihm plus ein kürzester Weg von ihm, und beide stehen schon in der Tabelle. Diese Art, eine große Antwort aus schon gefundenen kleineren zu bauen, heißt dynamische Programmierung. Mit negativen Kanten funktioniert es weiterhin, und eine negative Zahl auf der Diagonale verrät einen negativen Zyklus.

Häufig gestellte Fragen

Was ist der Floyd–Warshall-Algorithmus?

Ein Algorithmus, der den kürzesten Abstand zwischen allen Knotenpaaren in einem gewichteten Graphen findet. Er führt eine Tabelle der Abstände und prüft für jeden Knoten der Reihe nach, ob der Weg über diesen Knoten irgendein Paar kürzer macht.

Wie schnell ist Floyd–Warshall?

Er hat drei verschachtelte Schleifen über die n Knoten, also wächst der Aufwand mit n³, und die Tabelle braucht n² Einträge. Für Graphen mit einigen hundert Knoten ist das kein Problem. Für große, dünn besetzte Graphen ist es schneller, den Dijkstra-Algorithmus von jedem Knoten aus laufen zu lassen.

Kommt Floyd–Warshall mit negativen Kanten zurecht?

Ja, solange es keinen negativen Zyklus gibt. Gibt es einen, wird ein Eintrag auf der Diagonale negativ, und so erkennt Floyd–Warshall ihn.

Wie bekomme ich die Wege, nicht nur die Abstände?

Führen Sie eine zweite Tabelle mit dem nächsten Knoten auf dem Weg von i nach j. Wird ein Paar über k kürzer, übernehmen Sie den nächsten Knoten von i in Richtung k. Folgt man dieser Tabelle von i nach j, ergibt sich der Weg.

Wird mein Graph irgendwohin gesendet?

Nein. Der Graph wird in Ihrem Browser erzeugt und die Tabelle dort gefüllt, und Ihre letzten Einstellungen bleiben im lokalen Speicher dieses Browsers.

Bereit, es auszuprobieren?

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

Zum Editor