Theoretische Informatik

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.

Tripel Algorithmus
direkt ins Video springen
Floyd Warshall Algorithmus, auch Tripel Algorithmus genannt

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.

Tripel Algorithmus
direkt ins Video springen
Floyd Warshall Algorithmus – Beispiel

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.

Algorithmus von Floyd: k = 2
direkt ins Video springen
Floyd Algorithmus

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.

4.Schritt: k = 4

Floyd Algorithmus - Beispiel
direkt ins Video springen
Floyd Algorithmus

Im Anschluss setzt du k gleich 4. Hier gibt es allerdings keine Veränderungen. Nun sind wir also alle Knoten von k=1 bis N durchgegangen.

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.

Warshall Algorithmus - Beispiel
direkt ins Video springen
Warshall Algorithmus

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.


Andere Nutzer halten diese Inhalte aus dem Bereich „Theoretische Informatik“ für besonders klausurrelevant

Hallo, leider nutzt du einen AdBlocker.

Auf Studyflix bieten wir dir kostenlos hochwertige Bildung an. Dies können wir nur durch die Unterstützung unserer Werbepartner tun.

Schalte bitte deinen Adblocker für Studyflix aus oder füge uns zu deinen Ausnahmen hinzu. Das tut dir nicht weh und hilft uns weiter.

Danke!
Dein Studyflix-Team

Wenn du nicht weißt, wie du deinen Adblocker deaktivierst oder Studyflix zu den Ausnahmen hinzufügst, findest du hier eine kurze Anleitung. Bitte lade anschließend die Seite neu.