= Floyd-Warshall algorithm
{c}
{title2=$d_{ij}\leftarrow\min(d_{ij},d_{ik}+d_{kj})$}
The Floyd-Warshall algorithm computes all-pairs shortest <graph path> lengths in a finite weighted <directed graph> with no negative-length <cycles in a graph>. Initialize $d_{ii}=0$, use the arc cost for each existing directed <edge>, and use $+\infty$ when no arc exists. For $k=1,\ldots,n$, update every ordered pair $(i,j)$ by the displayed rule. The storage is $n^2$ lengths and the running time is $O(n^3)$.
For correctness, let $d_{ij}^{(k)}$ be the shortest simple <graph path> length whose intermediate <vertices> lie among the first $k$. A shortest allowed <graph path> either avoids $k$ or splits at its unique occurrence of $k$, giving the recurrence. Conversely, concatenate shortest paths through $k$ and remove any repeated-vertex sections; each such closed <walk> has nonnegative length, so removal cannot increase the length. This proves equality. The update can be performed in place because $d_{kk}=0$ and the $k$th row and column remain unchanged during stage $k$.
If negative-length <cycles in a graph> are present, a shortest <walk> may not exist and the recurrence need not compute shortest simple <graph paths>. Two optimal subpaths can concatenate into a repeated-vertex <walk> with a negative cycle; deleting that cycle increases its length. A negative diagonal entry in the algorithm's final array detects this obstruction to finite shortest-walk distances.
Back to article page
