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:
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:
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.
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:
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:
Beim vierten Schritt ändert sich nichts, da der "freigegebene" Knoten D keine ausgehende gerichtete Kanten besitzt. Die Tabelle bleibt also gleich:
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.
Dies war nun auch der letzte Schritt, da alle Knoten einmal "freigegeben" wurden. Es ergibt sich damit folgende Distanztabelle:
