Algorithmus von Floyd und Warshall

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.

Inhaltsverzeichnis

Beschreibung

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 der kürzesten Distanzen durch folgendes Verfahren bestimmen:

Algorithmus von Floyd

(1) Für alle i,j : d[i,j] = w[i,j]
(2) Für k = 1 bis n
(3)    Für alle Paare i,j
(4)        d[i,j] = min (d[i,j],d[i,k] + d[k,j])

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

w ist die Adjazenzmatrix, das heißt w[i,j] ist 1 falls eine Kante von i nach j existiert, 0 falls keine Kante existiert.

Die Matrix d wird so berechnet, dass d[i,j] gleich 1, genau dann, wenn ein Pfad von i nach j existiert:

Algorithmus von Warshall

(1) Für k = 1 bis n
(2)   Für i = 1 bis n
(3)     Falls d[i,k] = 1
(4)       Für j = 1 bis n
(5)         Falls d[k,j] = 1 : d[i,j] = 1

In Zeile (5) wird d[i,j] auf 1 gesetzt, genau dann, wenn ein Pfad von i nach k und ein Pfad von k nach j über Kanten mit Index kleiner als k 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 Diagonalen der Distanzmatrix.

Die Komplexität des Floyd-Warshall-Algorithmus liegt in  \mathcal{O}(n^3) , da die Zahl der Paare (i,j) quadratisch beschränkt ist.

Andere Verfahren zur Berechnung kürzester Pfade

Literatur

Weblinks


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Algorithmus von Bellman und Ford — Der Algorithmus von Bellman und Ford (nach seinen Erfindern Richard Bellman und Lester Ford) ist ein Algorithmus der Graphentheorie und dient der Berechnung der kürzesten Wege ausgehend von einem Startknoten in einem kantengewichteten Graphen.… …   Deutsch Wikipedia

  • Algorithmus von Dijkstra — Der Algorithmus von Dijkstra (nach seinem Erfinder Edsger W. Dijkstra) dient der Berechnung eines kürzesten Pfades zwischen einem Startknoten und einem beliebigen Knoten in einem kantengewichteten Graphen. Die Gewichte dürfen dabei nicht negativ… …   Deutsch Wikipedia

  • Floyd — ist ein Vorname und Familienname, siehe Floyd (Name) für Etymologie und Namensträger Orte in den Vereinigten Staaten: Floyd (Alabama) Floyd (Arkansas) Floyd (Georgia) Floyd (Iowa) Floyd (Kalifornien) Floyd (Kentucky) Floyd (Louisiana) Floyd… …   Deutsch Wikipedia

  • Floyd-Warshall-Algorithmus — 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. Er findet die Länge der kürzesten Wege zwischen allen Paaren …   Deutsch Wikipedia

  • Floyd Warshall Algorithmus — 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. Er findet die Länge der kürzesten Wege zwischen allen Paaren …   Deutsch Wikipedia

  • Warshall-Algorithmus — 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. Er findet die Länge der kürzesten Wege zwischen allen Paaren …   Deutsch Wikipedia

  • Tripel-Algorithmus — 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. Er findet die Länge der kürzesten Wege zwischen allen Paaren …   Deutsch Wikipedia

  • Dijkstras Algorithmus — Der Algorithmus von Dijkstra (nach seinem Erfinder Edsger W. Dijkstra) dient der Berechnung eines kürzesten Pfades zwischen einem Startknoten und einem beliebigen Knoten in einem kantengewichteten Graphen. Die Gewichte dürfen dabei nicht negativ… …   Deutsch Wikipedia

  • A-Stern-Algorithmus — Der A* Algorithmus („A Stern“ oder englisch „a star“) gehört zur Klasse der informierten Suchalgorithmen. Er dient in der Informatik der Berechnung eines kürzesten Pfades zwischen zwei Knoten in einem Graphen mit positiven Kantengewichten. Er… …   Deutsch Wikipedia

  • Dijkstra-Algorithmus — Animation des Dijkstra Algorithmus Der Algorithmus von Dijkstra (nach seinem Erfinder Edsger W. Dijkstra) ist ein Algorithmus aus der Klasse der Greedy Algorithmen und löst das Problem der kürzesten Pfade für einen gegebenen Startknoten. Er… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”