Algorithmus von Floyd und Warshall

Algorithmus der Graphentheorie

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.

BeschreibungBearbeiten

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   nach   durch  , dann sind die enthaltenen Teilpfade von   nach   und von   nach   schon minimal. Nimmt man also an, man kennt schon die kürzesten Wege zwischen allen Knotenpaaren, die nur über Knoten mit Index kleiner als   führen und man sucht alle kürzesten Wege über Knoten mit Index höchstens  , dann hat man für einen Pfad von   nach   zwei Möglichkeiten: Entweder er geht über den Knoten  , dann setzt er sich zusammen aus schon bekannten Pfaden von   nach   und von   nach  , oder es ist der schon bekannte Weg von   nach   über Knoten mit Index kleiner als  .

Angenommen der Graph ist gegeben durch seine Gewichtsmatrix  .

  ist das Gewicht der Kante von   nach  , falls eine solche Kante existiert. Falls es keine Kante von   nach   gibt, ist   unendlich.

Dann kann man die Matrix   der kürzesten Distanzen durch folgendes Verfahren bestimmen:

Algorithmus von Floyd
(1) Für alle  
(2) Für   bis  
(3)   Für alle Paare  
(4)      

Will man die transitive Hülle berechnen, ändert man den Algorithmus folgendermaßen ab:

  ist die Adjazenzmatrix, das heißt   ist 1 falls eine Kante von   nach   existiert, 0 falls keine Kante existiert.

Die Matrix   wird so definiert, dass  , genau dann, wenn ein Pfad von   nach   existiert:

Algorithmus von Warshall
(1) Für   bis  
(2)   Für   bis  
(3)     Falls  
(4)       Für   bis  
(5)         Falls  
(6)            

In Zeile (6) wird   auf 1 gesetzt, genau dann, wenn ein Pfad von   nach   und ein Pfad von   nach   über Kanten mit Index kleiner als   existiert.

Der Floyd-Algorithmus funktioniert auch, wenn die Kanten negatives Gewicht haben. Zyklen mit negativer Länge werden (anders als beim Bellman-Ford-Algorithmus) jedoch nicht erkannt und führen zu einem falschen Ergebnis. Erkennbar sind negative Zyklen aber im Nachhinein durch negative Werte auf der Hauptdiagonalen der Distanzmatrix. Um numerische Probleme zu vermeiden, sollte man dies aber nicht erst im Nachhinein testen, sondern jedes Mal, wenn in Zeile (6) ein Diagonalelement geändert wird.[1]

Die Komplexität des Floyd-Warshall-Algorithmus liegt in  , da die Zahl der Paare   quadratisch beschränkt ist.

Andere Verfahren zur Berechnung kürzester PfadeBearbeiten

LiteraturBearbeiten

WeblinksBearbeiten

EinzelnachweiseBearbeiten

  1. Stefan Hougardy: The Floyd–Warshall algorithm on graphs with negative cycles. In: Information Processing Letters. 110, Nr. 8–9, April 2010, S. 279–281.