Direkt zum Inhalt

Lexikon der Mathematik: Floyd-Warshall, Algorithmus von

liefert in einem zusammenhängenden und bewerteten Graphen G ohne Kreise negativer Länge mit einer Komplexität O(|E(G)|3 ) die kürzesten Wege zwischen allen Eckenpaaren des Graphen.

Die Algorithmen von Dijkstra und Moore-Bellman-Ford haben den Nachteil, daß man dabei immer nur kürzeste Wege erhält, die von einer Anfangsecke zu allen anderen Ecken führen. Will man jedoch die Entfernungen zwischen je zwei beliebigen Ecken ermitteln, so bietet sich der Algorithmus von Floyd-Warshall (1962) an, der aus der bewerteten Adjazenzmatrix eines Graphen die Distanzmatrix DG = ((dij)) produziert, wobei dij die Länge eines kürzesten Weges von der Ecke xi zur Ecke xj angibt, falls E(G) = {x1, x2,…, xn} gilt.

Besitzt G die Bewertung ϱ : K(G) → ℝ, so nennt man die (n × n)-Matrix BG = (ϱij) mit ϱij = ϱ(xixj), falls xixjK(G), und ϱij = ∞, falls xi und xj nicht adjazent sind, bewertete Adjazenzmatrix.

Im ersten Schritt des Floyd-Warshall Algorithmus wird nun die direkte Verbindung zweier Ecken mit der Länge eines Weges verglichen, der zusätzlich die Ecke x1 verwendet, und das Minimum in einer Matrix D1 abgespeichert. Im nächsten Schritt wird jeder Wert aus D1 mit der Länge eines entsprechenden Weges verglichen, der zusätzlich die Ecke x2 oder die Ecken x1 und x2 verwendet, und das Minimum in einer Matrix D2 abgespeichert, bis man schließlich im n-ten Schritt alle Ecken des Graphen berücksichtigt hat.

Wird zusätzlich in jedem Schritt in einer zweiten Matrix vermerkt, welche neue Ecke für den Aufbau des kürzesten Weges genutzt wurde, so lassen sich am Ende die dem Minimum entsprechenden kürzesten Wege an dieser Matrix ablesen.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos