Skip to interview prep
Apexed

376. Why is Floyd–Warshall a dynamic programming algorithm?

MediumDynamic programming

Technical
Show model answer

Define d_k[i][j] as the shortest path from i to j using only vertices 1..k as intermediates. Either the best path avoids vertex k, giving d_(k−1)[i][j], or it goes through k exactly once, giving d_(k−1)[i][k] + d_(k−1)[k][j]. So d_k[i][j] = min of those two, with d_0 equal to the edge weights (0 on the diagonal, infinity for missing edges).

Updating a single matrix in place with k as the outer loop is safe, because row k and column k do not change during iteration k. It is O(V³) time and O(V²) space, handles negative edges, and reports a negative cycle when any d[i][i] becomes negative. Keeping a 'next' matrix lets you reconstruct paths.

Why is Floyd–Warshall a dynamic programming algorithm — Data structures & algorithms interview question — Apexed