DE 
EnglishDefault
Українська
Polski🗺️ Floyd-Warshall — Kürzeste Wege zwischen allen Paaren
Floyd-Warshall findet kürzeste Wege zwischen jedem Knotenpaar in O(V³), indem über jeden Zwischenknoten relaxiert wird. Beobachte, wie sich die Distanzmatrix strafft, während der Pivot k voranschreitet.
Über diese Simulation
Diese Simulation führt den Floyd-Warshall-Algorithmus live auf einem kleinen zufälligen gerichteten Graphen mit 5 bis 7 Knoten aus. Sie füllt eine V×V-Distanzmatrix, indem sie jedes Paar (i, j) über einen Pivotknoten k relaxiert, einen Schritt der Dreifachschleife nach dem anderen, und lässt jede Zelle aufblitzen, sobald sie sich verbessert. Sobald der Pivot alle Knoten durchlaufen hat, wird der kürzeste Weg zwischen Quelle und Ziel deiner Wahl direkt auf dem Graphen hervorgehoben.
🔬 Was es zeigt
Ein gewichteter gerichteter Graph (ein zusammenhängender Ring plus einige zusätzliche zufällige Kanten), gerendert als Pfeile mit ihren Gewichten, neben einer live V×V-Distanzmatrix. Während der Pivot k voranschreitet, heben sich Zeile und Spalte für k hervor.
🎮 Bedienung
Stelle die Anzahl der Knoten (5-7) und Geschwindigkeit ein, dann drücke Play, um die Dreifachschleife automatisch zu animieren, oder Schritt, um genau einen Pivot k weiterzuschalten. Wähle Quelle und Ziel aus den Dropdowns.
💡 Wusstest du schon?
Floyd-Warshall benötigt keine Prioritätswarteschlange und keinen Neustart pro Quelle — drei einfache verschachtelte Schleifen über jeden Knoten lösen alle Paare auf einmal. Diese flache O(V³)-Kosten mit winzigem konstantem Faktor ist der Grund, warum es oft die praktische Wahl bei kleinen oder dichten Graphen ist.
Häufig gestellte Fragen
Was berechnet der Floyd-Warshall-Algorithmus?
Floyd-Warshall berechnet den kürzesten Weg zwischen jedem Knotenpaar in einem gewichteten Graphen auf einmal. Statt einen Einzelquellen-Algorithmus von jedem Knoten auszuführen, füllt er eine V×V-Distanzmatrix, wobei dist[i][j] die Länge des kürzesten Weges von i nach j ist.
Wie funktioniert die Pivot-Relaxation?
Der Algorithmus verwendet eine Dreifachschleife mit einem äußeren Pivot k. Für jedes Paar (i, j) fragt er, ob der Weg von i über k nach j kürzer ist als der aktuell beste: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]).
Warum ist Floyd-Warshall O(V³)?
Es gibt drei verschachtelte Schleifen, jede über alle V Knoten laufend: den Pivot k, die Quelle i und das Ziel j. Das ergibt V × V × V = V³ Relaxationsschritte, also ist die Zeitkomplexität O(V³).
Wie behandelt Floyd-Warshall negative Kanten und negative Zyklen?
Anders als Dijkstra toleriert Floyd-Warshall negative Kantengewichte und liefert weiterhin korrekte kürzeste Wege. Ein negativer Zyklus bedeutet jedoch, dass manche kürzesten Wege undefiniert sind, weil man endlos schleifen kann, um die Kosten zu senken.
Wie vergleicht sich Floyd-Warshall mit Dijkstra?
Dijkstra löst das Einzelquellen-Kürzeste-Wege-Problem und ist schnell auf dünn besetzten Graphen, benötigt aber nicht-negative Gewichte und liefert nur Wege von einer Quelle. Floyd-Warshall mit seinen flachen O(V³)-Kosten ist einfacher zu programmieren und gewinnt oft bei kleinen oder dichten Graphen.
Wo wird Floyd-Warshall in der Praxis eingesetzt?
Es wird für Routingtabellen in kleinen Netzwerken, die Berechnung des transitiven Abschlusses einer Relation, das Finden von Graphdurchmesser und Zentralität sowie das Lösen von Alle-Paare-Distanzabfragen in Karten, Spielen und Operations Research verwendet.