Tripel-Algorithmus

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 von Knoten eines gewichteten Graphen (engl. All Pairs Shortest Path Problem = APSP, oder auch: All Pairs Best Path Problem = APBP) in der Version Floyds oder die reflexive, transitive Hülle eines Graphen in der Version Warshalls. Beide Versionen wurden im Jahr 1962 vorgestellt und gehen eigentlich zurück auf einen Algorithmus, den Stephen Kleene im Jahr 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 kleiner oder gleich 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 können, allerdings werden Zyklen mit negativer Länge (anders als beim Bellman-Ford-Algorithmus) nicht erkannt und führen zu einem falschen Ergebnis. Erkennbar werden negative Zyklen aber im Nachhinein durch negative Werte auf der Diagonalen der Distanzmatrix.

Die Laufzeit des Floyd-Warshall-Algorithmus ist O(n3), denn die Zeile (4) wird weniger als n3 mal ausgeführt, da die Zahl der Paare i,j quadratisch beschränkt ist.

Andere Verfahren zur Berechnung kürzester Pfade

Literatur

  • Robert W. Floyd: Algorithm 97 (SHORTEST PATH), in Communications of the ACM, 5(6), p. 345, 1962.
  • Stephen Warshall: A Theorem on Boolean Matrices, in Journal of the ACM, 9(1), pp. 11-12, 1962.

Weblinks


Wikimedia Foundation.

Игры ⚽ Нужен реферат?

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

  • 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… …   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

  • ElGamal-Algorithmus — Das Elgamal Kryptosystem (auch al Dschamal Kryptosystem) ist ein Schema zur Verschlüsselung, das auf dem mathematischen Problem des diskreten Logarithmus beruht. Elgamal ist ein asymmetrischer Verschlüsselungsalgorithmus aufbauend auf der Idee… …   Deutsch Wikipedia

  • Elgamal-Algorithmus — Das Elgamal Kryptosystem (auch al Dschamal Kryptosystem) ist ein Schema zur Verschlüsselung, das auf dem mathematischen Problem des diskreten Logarithmus beruht. Elgamal ist ein asymmetrischer Verschlüsselungsalgorithmus aufbauend auf der Idee… …   Deutsch Wikipedia

  • Erweiterter euklidischer Algorithmus — Der erweiterte euklidische Algorithmus ist ein Algorithmus aus dem mathematischen Teilgebiet der Zahlentheorie. Er berechnet neben dem größten gemeinsamen Teiler zweier natürlicher Zahlen a und b noch zwei ganze Zahlen s und t, die die folgende… …   Deutsch Wikipedia

  • Lempel-Ziv-Storer-Szymanski-Algorithmus — Der Lempel Ziv Storer Szymanski Algorithmus (LZSS) ist ein Algorithmus zur verlustfreien Datenkompression auf Basis von LZ77. Er wurde 1982 von James A. Storer und Thomas G. Szymanski im Journal of the ACM veröffentlicht, einer Fachzeitschrift… …   Deutsch Wikipedia

  • Spektraltest — Der Spektraltest ist eine Methode, mit der überprüft werden kann, ob gegebene Zufallszahlen tatsächlich stochastisch voneinander unabhängig sind, oder ob das Gegenteil der Fall ist, d. h. bereits „gewürfelte“ Werte die folgenden Werte… …   Deutsch Wikipedia

  • Elementare Zahlentheorie — Ursprünglich ist die Zahlentheorie (auch: Arithmetik) ein Teilgebiet der Mathematik, das sich allgemein mit den Eigenschaften der ganzen Zahlen und insbesondere mit den Lösungen von Gleichungen in den ganzen Zahlen (Diophantische Gleichung)… …   Deutsch Wikipedia

Share the article and excerpts

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