templates · Shortest paths & spanning trees

Floyd–Warshall (all pairs)

  • You need the shortest distance between every pair of nodes
  • The graph is small: n up to about 100–400 nodes
  • Questions like "how many cities are within distance d of each city"

Floyd–Warshall

the one rule

The invariant

After the outer loop has finished k, d[i][j] is the shortest path that uses only nodes 0..k as middle stops.

write it from memory

The template

javajava.util.*
/** Shortest distance between every pair. edges[i] = {u, v, w}, directed. INF = no path. */static long[][] allPairs(int n, int[][] edges) {    final long INF = Long.MAX_VALUE / 4;    long[][] d = new long[n][n];    for (long[] row : d) Arrays.fill(row, INF);    for (int i = 0; i < n; i++) d[i][i] = 0;    for (int[] e : edges)                             // undirected? also set d[v][u]        d[e[0]][e[1]] = Math.min(d[e[0]][e[1]], e[2]);    for (int k = 0; k < n; k++)                       // now k may be a middle stop        for (int i = 0; i < n; i++) {            if (d[i][k] == INF) continue;             // INF guard: no way to reach k            for (int j = 0; j < n; j++)                if (d[k][j] != INF && d[i][k] + d[k][j] < d[i][j])                    d[i][j] = d[i][k] + d[k][j];        }    return d;                                         // d[i][i] < 0: i sits on a negative cycle}

Three loops, and k must be the outermost. Bas itna yaad rakho: "k, i, j" — the middle stop comes first.

fill in the blanks — only these lines change per problem

  1. line 7How edges go into the table. For an undirected graph, set both d[u][v] and d[v][u].
  2. line 13The combine rule. Shortest path uses + and min; other problems use max, && (can i reach j?) or a product.
  3. line 16What you read from the table: one row, a count per row, or d[i][i] < 0 for a negative cycle.

complexity

What it costs

time O(n³)
Three nested loops over n nodes. n = 100 is 10⁶ steps; n = 400 is 6.4 × 10⁷, still fine in Java.
space O(n²)
One n × n distance table, updated in place.

watch out

Common bugs

  • Putting k in the inner loop. The code still runs but gives wrong answers.
  • Using Integer.MAX_VALUE as INF and adding two of them: the sum overflows to a negative number.
  • Forgetting d[i][i] = 0, or forgetting the reverse edge in an undirected graph.

use it

Practise it on

learn it properly