Floyd Warshall Algorithmus
Wie findet man eigentlich die kürzesten Wege zwischen allen möglichen Knotenpaaren in einem Graphen? Und wieviel kosten diese? Die Lösung ist der Floyd-Warshall Algorithmus!
Inhaltsübersicht
Algorithmus von Floyd und Warshall bzw. Tripel Algorithmus
Der Floyd-Warshall Algorithmus, der auch Tripel-Algorithmus genannt wird, ist ein Methode, um kürzeste Wege innerhalb eines Graphen zu berechnen. Er ermittelt aber nicht nur die kürzeste Distanz zwischen zwei Knoten, sondern zwischen allen Knotenpaaren eines gewichteten Graphen .
Der Algorithmus kann auch mit negativen Kantengewichten umgehen. Hat allerdings ein Zyklus eine negative Länge, führt der Floyd-Warshall Algorithmus zu einem falschen Ergebnis.
Idee des Algorithmus
Der Algorithmus besteht im Grunde aus 2 Teilen: Der Teil von Floyd zur Berechnung der kürzesten Distanzen zwischen den Knoten und der Teil von Warshall zum Konstruieren der kürzesten Wege. Fügt man beide zusammen, erhält man den Floyd-Warshall-Algorithmus. Aber wie funktioniert der nun genau?
Zuerst erstellt man eine Gewichtsmatrix W mit den Matrixeinträgen W[i, j]. Dann geht der Algorithmus in einer Hauptschleife alle Knoten k von 1 bis N durch. In jeder Iteration versucht er alle Wege von i nach j durch die Wege (i, k) und (k, j) zu verbessern. Falls der vermeintliche Umweg zu einer Verbesserung führt, wird die Matrix aktualisiert.
Formal werden die aktuellen Pfadkosten folgendermaßen ermittelt:
d[i, j] = min {d[i, j], d[i, k] + d[k, j]}
Puhh, das klingt jetzt für dich doch ziemlich kompliziert? Kein Problem! Wir schauen uns das einfach gemeinsam an einem Beispiel an und du wirst es ruck zuck verstehen.
Floyd-Warshall-Algorithmus Beispiel
Wir wollen uns einen gerichteten, gewichteten Graphen genauer ansehen.
Kürzeste Wege – Floyd-Algorithmus
Zuerst erstellst du eine Gewichtsmatrix zu dem Graphen. Auf der Diagonalen trägst du überall eine Null ein. Falls es eine Kante zwischen den zwei Knoten i und j gibt, ist der Matrixeintrag W[i, j] das Gewicht der Kante von i nach j. Falls es keine Kante gibt, die die Knoten verbindet, trägst du unendlich in die Zelle ein.
1.Schritt: k = 1
Im ersten Schritt des Algorithmus setzt du k=1. Das heißt, dass du dir genauer anschaust ob Knoten 1 als Verbindungsknoten für andere Knoten dienen kann. Da Knoten 1 jedoch eine Quelle ist, was heißt, dass keine gerichtete Kante in den Knoten eingeht, ist das nicht der Fall.
2.Schritt: k = 2
Somit kannst du direkt k auf 2 setzen und Knoten 2 quasi „freigeben“.
Nun siehst du, dass du über Knoten 2 von Knoten 1 zu Knoten 4 gelangen kannst. Die bisherige Verbindung von 1 zu 4 beträgt unendlich. Die Verbindung über Knoten 2 ist also mit 10 + 4 = 14 günstiger.
Aber wie war das jetzt nochmal mit dieser Formel? Ganz einfach:
d[1, 4] = min {d[1, 4], d[1, 2] + d[2, 4]}
= min {∞, 10 + 4}
= min {∞, 14}
= 14
Die Distanz von 1 nach 4 ist gleich das Minimum aus der direkten Distanz [1, 4] und der Distanz [1, 2] plus [2, 4]. Also das Minimum von Unendlich und 10 plus 4. Und somit 14 – wie wir uns das schon logisch überlegt hatten.
Auch für Knoten 3 ergibt sich über Knoten 2 ein weiterer Weg zu Knoten 4. Betrachten wir auch das einmal formal:
d[3, 4] = min {d[3, 4], d[3, 2] + d[2, 4]}
= min {5, 2 + 4}
= 5
Das Minimum ist hier 5. Durch einen Umweg würdest du dir also nichts sparen.
3.Schritt: k = 3
Weiter geht es mit k = 3. Durch den Weg über Knoten 3 kommst du zu Kosten von 5 von Knoten 1 zu Knoten 2.
Auch der Weg von Knoten 1 zu Knoten 4 wird günstiger, wenn du über Knoten 3 gehst. Du trägst also den neuen Wert, nämlich 8, in die Tabelle ein.
Warshall-Algorithmus – Kürzeste Wege konstruieren
Die Matrix liefert allerdings nur die kürzesten Distanzen zwischen den Knoten, aber nicht den tatsächlichen Weg. Hierfür ist der Warshall-Teil des Algorithmus zuständig.
Für den benötigen wir eine zweite Matrix, die wir F nennen. Zu Beginn steht in jeder Zelle der Startknoten der jeweiligen Kante, falls sie existiert.
Wird nun wie im Laufe des Floyd-Algorithmus ein kürzerer Weg gefunden, wird die Matrix F aktualisiert. Der Weg von Knoten 1 zu Knoten 4 führt über Knoten 3. Knoten 3 ist also der neue Vorgänger von Knoten 4 und wird somit in die Matrix eingetragen. Als aktuellen Vorgänger von Knoten 2 auf dem Weg von 1 nach 2 wird ebenfalls 3 eingetragen.
Aus der Matrix F können wir nun zum Beispiel den kürzesten Weg von Knoten 1 zu Knoten 2 konstruieren. In der Zelle [1,2] steht der Vorgänger von Knoten 2. Somit führt der kürzeste Weg von Knoten 1 über Knoten 3 zu Knoten 2.
Negative Zyklen
Aber wie kann jetzt der Algorithmus negative Zyklen erkennen?
Falls in dem Graphen ein Zyklus mit einer negativen Summe der Kantengewichte existiert, so hat nach Ablauf des Algorithmus ein Knoten eine negative Distanz zu sich selbst. Der Algorithmus kann dies abfangen und so eine entsprechende Fehlerbehandlung durchführen.
Pseudocode des Floyd-Warshall Algorithmus
Hier siehst du einen möglichen Pseudocode, der sowohl den Floyd-, als auch den Warshall-Algorithmus beinhaltet:
Distanzmatrix mit Kanten initialisieren
Nachfolgermatrix mit Zeilennamen initialisieren
für jedes i von 1 bis Anzahl Knoten:
für jedes j von 1 bis Anzahl Knoten:
für jedes k von 1 bis Anzahl Knoten:
wenn Distanz[i][j] > ( Distanz[i][k] + Distanz [k][j] ):
Distanz[i][j] = ( Distanz[i][k] + Distanz [k][j] )
Nachfolger[i][j] = Nachfolger[k][j]
Sehr gut! Jetzt weist du auch was hinter dem Algorithmus steckt der genau genommen aus zwei Algorithmen besteht und du kannst kürzeste Wege berechnen und konstruieren.