Der Algorithmus von Floyd und Warshall (auch Floyd-Warshall-Algorithmus oder Tripel-Algorithmus), benannt nach Robert Floyd und Stephen Warshall, ist ein Algorithmus der Graphentheorie. In Floyds Version findet er die kürzesten Pfade zwischen allen Paaren von Knoten eines Graphen und berechnet deren Länge (APSP, all-pairs shortest path). In Warshalls Version findet er die transitive Hülle eines Graphen. Beide Versionen wurden 1962 vorgestellt und gehen auf einen Algorithmus zurück, den Stephen Kleene 1956 im Zusammenhang mit regulären Ausdrücken veröffentlicht hat.
Der Floyd-Warshall-Algorithmus basiert auf dem Prinzip der dynamischen Programmierung. Der Floyd-Algorithmus geht von folgender Beobachtung aus:
Geht der kürzeste Weg von u nach v durch w, dann sind die enthaltenen Teilpfade von u nach w und von w nach v schon minimal. Nimmt man also an, man kennt schon die kürzesten Wege zwischen allen Knotenpaaren, die nur über Knoten mit Index kleiner als k führen, und man sucht alle kürzesten Wege über Knoten mit Index höchstens k, dann hat man für einen Pfad von u nach v zwei Möglichkeiten: Entweder er geht über den Knoten k, dann setzt er sich zusammen aus schon bekannten Pfaden von u nach k und von k nach v, oder es ist der schon bekannte Weg von u nach v über Knoten mit Index kleiner als k. Angenommen, der Graph ist gegeben durch seine Gewichtsmatrix w. w[i,j] ist das Gewicht der Kante von i nach j, falls eine solche Kante existiert. Falls es keine Kante von i nach j gibt, ist w[i,j] unendlich. Dann kann man die Matrix d die kürzesten Distanzen bestimmen.
Der Floyd-Warshall-Algorithmus basiert auf dem Prinzip der dynamischen Programmierung. Der Floyd-Algorithmus geht von folgender Beobachtung aus:
Geht der kürzeste Weg von u nach v durch w, dann sind die enthaltenen Teilpfade von u nach w und von w nach v schon minimal. Nimmt man also an, man kennt schon die kürzesten Wege zwischen allen Knotenpaaren, die nur über Knoten mit Index kleiner als k führen, und man sucht alle kürzesten Wege über Knoten mit Index höchstens k, dann hat man für einen Pfad von u nach v zwei Möglichkeiten: Entweder er geht über den Knoten k, dann setzt er sich zusammen aus schon bekannten Pfaden von u nach k und von k nach v, oder es ist der schon bekannte Weg von u nach v über Knoten mit Index kleiner als k. Angenommen, der Graph ist gegeben durch seine Gewichtsmatrix w. w[i,j] ist das Gewicht der Kante von i nach j, falls eine solche Kante existiert. Falls es keine Kante von i nach j gibt, ist w[i,j] unendlich. Dann kann man die Matrix d die kürzesten Distanzen bestimmen.
...als Startbare
Datei
Software zur Veranschaulichung der Zahlenumrechung
