Floyd-Warshall-Algorithmus

Der Floyd-Warshall-Algorithmus, oder auch Tripel-Algorithmus genannt, ist nach Robert Floyd und Stephen Warshall benannt. Mit Hilfe dieses Algorithmus lassen sich in einem Graphen die kürzesten Wege berechnen. Im Gegensatz zum Dijkstra-Algorithmus können die Kanten auch negative Gewichte besitzen. Allerdings werden Zyklen mit negativer Länge nicht erkannt und führen zu einem falschen Ergebnis.

Floyd-Warshall-Algorithmus Beispiel

Nachfolgend ein Beispiel zum Floyd-Warshall-Algorithmus für das bessere Verständnis. Man gehe von folgenden Graphen aus:

Beispiel Graph für Floyd-Warshall-Algorithmus

Zu Beginn des Algorithmus wird die Distanzmatrix aus dem gegeben Graph abgelesen. Da die Knoten von sich selber immer erreichbar sein sollen, wird in der Diagonale eine 0 eingetragen. Anschließend werden noch die Distanzen der direkten Nachbarn hinzugefügt. So gibt es beispielsweise eine Kante zwischen dem Knoten A und dem Knoten B mit der Distanz 2. Also trägt man in Zeile A und Spalte B den Wert 2 ein. So verfährt man mit allen direkten Nachbarn. Anschließend werden die nun noch leeren Felder mit dem Wert Unendlich aufgefüllt. Es ergibt sich demnach folgende Tabelle:

Beispiel Graph für Floyd-Warshall-Algorithmus

Im ersten Schritt wird nun Knoten A "freigegeben". Man schaut also, ob Knoten A für andere Knoten als Verbindungsknoten fungieren könnte. Da an Knoten A aber keine gerichtete Kante ankommt, ist dies nicht der Fall. Im ersten Schritt ändert sich unsere Tabelle also nicht.

Erster Schritt im Floyd-Warshall-Algorithmus

Nach Knoten A wird nun Knoten B "freigegeben" und geschaut ob über Knoten B ein anderer Knoten einen anderen Knoten erreichen kann. Dies ist nun der Fall, da Knoten B eine gerichtete Kante zu Knoten D hat und Knoten A ein gerichtete Kante zu Knoten B, kann nun Knoten A über Knoten B den Knoten D erreichen. Dafür wird die Entfernung von Knoten A zu Knoten B - 2 - mit der Entfernung von Knoten B zu Knoten D - 9 - aufsummiert. Anschließend schreibt man die aufsummierte Distanz - 11 (2+9) - in Zeile A und Spalte D. Darüber hinaus kann nun Knoten C über Knoten B zu Knoten D. Auch hier schreibt man die neue Entfernung 7+9=16 in die Tabelle. Weitere Änderungen ergeben sich nicht. Somit lautet die geänderte Tabelle:

Zweiter Schritt im Floyd-Warshall-Algorithmus

Im dritten Schritt folgt die "Freigabe" von Knoten C. Damit hat Knoten A nun eine Verbindung zu Knoten E mit der Distanz: 3+5 = 8. Zusätzlich hat Knoten A über Knoten C auch eine Verbindung zu Knoten B mit der Distanz 10. Da die aber schon eingetragene Distanz zwischen A und B niedriger ist, gibt es hier keine Veränderung. Auch sonst ändert sich nichts, sodass man zur folgende Tabelle kommt:

Dritter Schritt im Floyd-Warshall-Algorithmus

Beim vierten Schritt ändert sich nichts, da der "freigegebene" Knoten D keine ausgehende gerichtete Kanten besitzt. Die Tabelle bleibt also gleich:

Vierter Schritt im Floyd-Warshall-Algorithmus

Im fünften Schritt wird Knoten E "freigegeben". Damit wird zwar kein Knoten, der bisher unerreichbar für andere Knoten ist, nun erreichbar, dafür ändern sich aber gleich zwei Werte. Über Knoten E ist nämlich der Weg von Knoten C zu Knoten D nämlich kürzer, sodass der alte Weg über Knoten B mit Distanz 16 mit dem neuen Wert Distanz 6 ersetzt wird. Und auch die Distanz zwischen A und D über C und nun E ist niedriger als die bisherige Distanz über B. Dementsprechend wird auch dieser Eintrag aktualisiert. Weitere Änderungen gibt es nicht.

Fünfter Schritt im Floyd-Warshall-Algorithmus

Dies war nun auch der letzte Schritt, da alle Knoten einmal "freigegeben" wurden. Es ergibt sich damit folgende Distanztabelle:

Endtabelle des Floyd-Warshall-Algorithmus