GeeksforGeeks Medium

Floyd–Warshall Algorithm

Shortest distances between all pairs of vertices, in one dynamic-programming sweep.

graphshortest-pathdpall-pairs

02

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.

03

Approach

1

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.

2

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.

3

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.

04

Solution & live demo

python

▶1def floyd_warshall(n, edges):
▶2    INF = float("inf")
▶3    d = [[0 if i == j else INF for j in range(n)] for i in range(n)]
▶4    for u, v, w in edges:
▶5        d[u][v] = min(d[u][v], w)
▶6    for k in range(n):            # k OUTERMOST
▶7        for i in range(n):
▶8            for j in range(n):
▶9                if d[i][k] + d[k][j] < d[i][j]:
▶10                    d[i][j] = d[i][k] + d[k][j]
▶11    return d

05

Edge cases

k must be the outer loop

Swapping the loop order silently produces wrong answers — a classic bug.

Negative cycle

Detected by a negative value on the diagonal.

Disconnected pairs

Remain ∞.

06

Complexity

Time

O(V³)

Space

O(V²)

Worth it when all pairs are needed; otherwise run Dijkstra per source.