Floyd–Warshall Algorithm
Shortest distances between all pairs of vertices, in one dynamic-programming sweep.
Open on GeeksforGeeks ↗Intuition
Ask a smaller question: what is the shortest path from i to j if it may only route through vertices numbered below k? Start with k = 0 (direct edges only) and admit one more intermediate at a time. Admitting k either helps — via i→k→j — or it does not. After every vertex has been admitted, the matrix holds true shortest paths.
All-pairs shortest paths in three nested loops. The meaning of k is the whole algorithm: after iteration k, d[i][j] is the best path using only vertices 0..k as intermediates. That's why k must be outermost — it's the DP dimension being built up, not just another index.
Approach
Initialise the matrix
d[i][j] = edge weight if one exists, 0 on the diagonal, ∞ otherwise. This is the answer when no intermediates are allowed.
Admit one intermediate at a time
For each k, for every pair (i, j): d[i][j] = min(d[i][j], d[i][k] + d[k][j]). The k-loop must be outermost — that is what makes the DP layer correct.
Negative cycles show on the diagonal
If any d[i][i] ends up negative, vertex i sits on a negative cycle: it can return to itself at a profit.
Solution & live demo
Common pitfalls
Putting k in the wrong loop position
for i in range(n):
for j in range(n):
for k in range(n):for k in range(n):
for i in range(n):
for j in range(n):The single most common error here. With k innermost you finalise d[i][j] before all intermediates have been considered, so multi-hop paths are missed. k is the DP layer — every pair must be updated for a given k before moving to the next.
Initialising the diagonal to infinity
d = [[INF] * n for _ in range(n)]
d = [[0 if i == j else INF for j in range(n)] for i in range(n)]
The distance from a vertex to itself is 0, and that zero is the base case every path composition relies on. Leaving it infinite blocks paths that route through a vertex back to itself.
Overwriting parallel edges instead of taking the minimum
d[u][v] = w
d[u][v] = min(d[u][v], w)
If the input lists two edges between the same pair, the later one wins outright and a cheaper earlier edge is lost. Keeping the minimum is safe regardless of input order.
Edge cases
Swapping the loop order silently produces wrong answers — a classic bug.
Detected by a negative value on the diagonal.
Remain ∞.