Floyd-Warshall

Graphs O(V³) O(V²)

All-pairs shortest paths by dynamic programming: round k asks every pair whether a stopover at node k shortens their path.

i\j	0	1	2	3
0	0	3	∞	7
1	8	0	2	∞
2	5	∞	0	1
3	2	∞	∞	0

k0123round k = allowed stopover

1/41

Start from the edge matrix: dist[i][j] = direct edge (∞ = none).

Invariantdist[i][j] is the shortest path that stops over only at nodes < k.

computingreads fromfilled

floyd-warshall.c

#define V 4
#define INF 1000000
 
void floydWarshall(int dist[V][V]) {
    for (int k = 0; k < V; k++) {
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                if (dist[i][k] + dist[k][j] < dist[i][j])
                    dist[i][j] = dist[i][k]
                               + dist[k][j];
            }
        }
    }
}

How Floyd-Warshall works

Dynamic programming over intermediate nodes: after round k, dist[i][j] is the shortest path using only nodes 0..k as stopovers. Round k asks one question per pair — is going through k shorter?

Worst case

Θ(V³) always — but with a tiny constant and no data structures.

When to use it

All-pairs shortest paths on small/dense graphs; handles negative edges (no negative cycles).