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

// 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

TimeThree nested loops over all V nodes

Cubic\(O(V^3)\)

SpaceFull V×V distance matrix

Quadratic\(O(V^2)\)

Negative weight supportUnlike Dijkstra

Yes—

Negative cycle detectiondist[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?

Bellman-Ford Algorithm

Shortest paths with negative weights — and negative cycle detection

→

Dijkstra's Algorithm

GPS for graphs — find the cheapest route from one node to all others

→