Graphs5 min read

Floyd-Warshall Algorithm

All-pairs shortest paths in one elegant triple loop
time: \(O(V^3)\)space: \(O(V^2)\)

Dijkstra and Bellman-Ford answer: what is the cheapest route from one source to everywhere? But what if you need the cheapest route between every pair of nodes? You could run Dijkstra V times — or you could use Floyd-Warshall, a clean dynamic programming algorithm that solves all pairs in one pass.

Floyd-Warshall handles negative edge weights (but not negative cycles). It is ideal for small, dense graphs where you need a complete distance matrix — a table showing the shortest distance from every node to every other node.

The DP recurrence

For each possible intermediate node k, check whether routing through k makes the path from i to j cheaper.

pseudocode
1
2
3
4
5
6
7
8
9
// Initialize:
// dist[i][j] = edge weight if direct edge exists, else Infinity
// dist[i][i] = 0


for k from 0 to V-1:
  for i from 0 to V-1:
    for j from 0 to V-1:
      if dist[i][k] + dist[k][j] < dist[i][j]:
        dist[i][j] = dist[i][k] + dist[k][j]

After all V outer iterations, dist[i][j] holds the shortest distance from node i to node j through any combination of intermediate nodes.

◈ Watch Floyd-Warshall

← → arrow keys to step · click elements to interact

Floyd-Warshall: All-Pairs Shortest Paths

INF = float('inf')


def floyd_warshall(dist):
    """dist is an n x n matrix. dist[i][j] = weight, INF if no edge."""
    n = len(dist)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist


# 4 nodes. INF = no direct edge.
dist = [
    [0,   3,   INF, 7  ],
    [8,   0,   2,   INF],
    [5,   INF, 0,   1  ],
    [2,   INF, INF, 0  ]
]
result = floyd_warshall(dist)
for row in result:
    print([x if x != INF else 'INF' for x in row])
Output
[0, 3, 5, 6]
[5, 0, 2, 3]
[3, 6, 0, 1]
[2, 5, 7, 0]

Tracing a 4-node example

Nodes: A, B, C, D. Edges: A→B=3, B→C=2, A→C=10, C→D=1, B→D=8.

Initially dist[A][D] = ∞ (no direct edge). After considering B as intermediate: dist[A][B] + dist[B][D] = 3+8 = 11 — update. After considering C: dist[A][C] + dist[C][D] = 5+1 = 6 (A→B→C = 5) — update to 6. Final shortest path A→D is 6, via A→B→C→D.

Negative cycle detection

After the algorithm, check the diagonal. dist[i][i] should always be 0. If dist[i][i] < 0, there is a negative-weight cycle passing through node i — the shortest path is undefined.

When to use Floyd-Warshall

  • V is small (up to a few hundred nodes) — \(O(V^3)\) becomes too slow for thousands
  • You need the shortest distance between all pairs, not just from one source
  • The graph may have negative edge weights (but no negative cycles)

For large sparse graphs, running Dijkstra from each node is usually faster: \(O(V × (V+E)\) log V) vs \(O(V^3)\).

Note: The triple loop looks intimidating but the question it asks each iteration is simple: can I get from i to j more cheaply by stopping at k? Ask that for every possible k, i, and j.

Complexity

Time
Three nested loops over all V nodes
Cubic \(O(V^3)\)
Space
Full V×V distance matrix
Quadratic \(O(V^2)\)
Negative weight support
Unlike Dijkstra
Yes —
Negative cycle detection
dist[i][i] < 0 signals a negative cycle
Yes (check diagonal) \(O(V)\)

Detect Negative Cycles (Floyd-Warshall)

INF = float('inf')


def floyd_warshall_neg_cycle(dist):
    n = len(dist)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    # Negative cycle: dist[i][i] < 0 for any i
    return any(dist[i][i] < 0 for i in range(n))


# No negative cycle
d1 = [[0,1,INF],[INF,0,2],[INF,INF,0]]
print(floyd_warshall_neg_cycle(d1))  # False


# With negative cycle: 0->1->2->0 = 1+2-4 = -1
d2 = [[0,1,INF],[INF,0,2],[-4,INF,0]]
print(floyd_warshall_neg_cycle(d2))  # True
Output
False
True
Challenge

Quick check

What does dist[i][j] represent after Floyd-Warshall completes?

Continue reading