liefert in einem zusammenhängenden und bewerteten GraphenG ohne Kreise negativer Länge mit einer Komplexität O(|E(G)|³ ) 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 D_G = ((d_ij)) produziert, wobei d_ij die Länge eines kürzesten Weges von der Ecke x_i zur Ecke x_j angibt, falls E(G) = {x₁, x₂,…, x_n} gilt.

Besitzt G die Bewertung ϱ : K(G) → ℝ, so nennt man die (n × n)-Matrix B_G = (ϱ_ij) mit ϱ_ij = ϱ(x_ix_j), falls x_ix_j ∈ K(G), und ϱ_ij = ∞, falls x_i und x_j 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 x₁ verwendet, und das Minimum in einer Matrix D¹ abgespeichert. Im nächsten Schritt wird jeder Wert aus D¹ mit der Länge eines entsprechenden Weges verglichen, der zusätzlich die Ecke x² oder die Ecken x₁ und x₂ verwendet, und das Minimum in einer Matrix D² 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.