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.
Studyflix vernetzt: Hier ein Video aus einem anderen Bereich
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.
Floyd Warshall Algorithmus — häufigste Fragen
(ausklappen)
Floyd Warshall Algorithmus — häufigste Fragen
(ausklappen)-
Was ist der Unterschied zwischen dem Dijkstra-Algorithmus und dem Floyd-Warshall-Algorithmus?Den Dijkstra-Algorithmus wendet man typischerweise an, um die kürzesten Wege von einem Startknoten zu allen anderen Knoten zu berechnen, während man mit dem Floyd-Warshall-Algorithmus die kürzesten Distanzen zwischen allen Knotenpaaren in einem Graphen erhält. Beim Dijkstra-Algorithmus arbeitet man schrittweise von der Quelle aus, beim Floyd-Warshall-Algorithmus aktualisiert man systematisch eine Distanzmatrix in einer Dreifachschleife.
-
Was ist ein Beispiel aus dem realen Leben für den Floyd-Warshall-Algorithmus?Ein reales Beispiel ist ein System, mit dem man für ein ganzes Straßennetz oder ein Firmennetzwerk die kürzesten Verbindungen zwischen allen Standorten vorberechnet. Die Kosten können dabei etwa Fahrzeit, Entfernung oder Transportkosten sein, je nachdem, was als Kantengewicht im Graphen modelliert wird.
-
Was ist das Floyd-Algorithmus-Programm?Mit „Floyd-Algorithmus-Programm“ meint man meist eine Implementierung des Floyd-Teils des Floyd-Warshall-Algorithmus, also den Programmcode oder Pseudocode, der die Distanzmatrix iterativ verbessert. Dabei werden für jedes Knoten-Triple
potenziell günstigere Wege über den Zwischenknoten 
in die Matrix übernommen.
-
Wie liest man aus der Vorgänger- oder Nachfolger-Matrix den kürzesten Pfad zwischen 2 Knoten ab?Aus einer Vorgänger-Matrix liest man den kürzesten Pfad ab, indem man beim Zielknoten startet und über die eingetragenen Vorgänger schrittweise zurück bis zum Startknoten geht und die Knotenreihenfolge danach umdreht.
Nach Beantwortung speichern wir deine Antwort, um Studyflix zu verbessern. Mehr dazu erfährst du in unserer Datenschutzerklärung.
Graphenalgorithmen verstehen
Der Floyd-Warshall-Algorithmus gehört zu den Graphenalgorithmen und ist ein wichtiges Beispiel für kürzeste Wege in gewichteten Graphen. Du vergleichst in diesem Themenfeld verschiedene Algorithmen, Matrizen und Wege in Graphen. So wird klar, wie Knoten, Kanten und Gewichte zusammenhängen und warum verschiedene Verfahren je nach Problem anders arbeiten. Weitere Videos dazu findest du in unserem Informatikbereich.
