Floyd-Warshall-Algorithmus

Der Floyd-Warshall-Algorithmus ist ein all-pairs shortest paths Algorithmus zur bestimmung kürzester Wege in gewichteten, gerichteten Graphen.

Idee

• Der Algorithmus nutzt die Entwurfsmethode der Dynamische Programmierung
• Als Eingabe bekommt er die Gewichtungsmatrix
• Schritt für Schritt wird über jeden Knoten iteriert und geschaut, ob ein Weg von nach unter Verwendung dieses Knotens billiger wird:

Beispiel

graph LR
2-->|8|1
2-->|2|3
3-->|5|1
3-->|1|4
1-->|3|2
4-->|2|1
1-->|7|4

Iterationen:

• : Da zwischen Start- und Endknoten andere Knoten liegen dürfen, entspricht diese Matrix der Gewichtungsmatrix .
• : Hier stehen alle kürzesten Wege, wenn man als Zwischenknoten den Knoten erlaubt. Berechnung:

Anmerkungen:

• Für bleiben die erste Zeile und die erste Spalte unberührt, für die zweite usw.
  Das liegt daran, dass diese Wege ja schon bei k starten oder enden, ein Einbezug des Knotens k kann den Weg also gar nicht verkürzen. Gibt es keine negativen Zyklen im Graphen, ist jeder Wert auf der Diagonalen gleich .

Implementierung

Pseudocode

Sei ein gerichteter Graph ohne negativen Zyklus gegeben durch die Matrix .

• Algorithmus FloydWarshall()
  • Für bis
    • Sei eine Matrix
    • Für bis
      • Für bis
  • Rückgabe:

Durch die 3 Schleifen hat der Algorithmus eine Laufzeit von