Floyd-Warshall algorithm ($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,\dots ,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.