The Floyd-Warshall algorithm is a [[dynamic programming]] algorithm to solve the [[all pairs shortest path]] problem. ``` for k = 1 to n: for i = 1 to n: for j = 1 to n: D^k[i, j] = min(D^{k-1}, D^{k-1}(i, k) + D^{k-1}(k_{ij})) ``` The running time is $\theta(n^3)$.