PK

PKBytes

Explore tracks
Chapter 35: Shortest Paths and Weighted Graph Search
35.06Intermediate / Advanced4 topics15 min4 interactive animations

Floyd-Warshall

Floyd-Warshall computes the shortest distance between every pair of vertices with three nested loops, by allowing one more intermediate vertex in each round; it handles negative edges and exposes negative cycles on the diagonal.

Learning goals

  • Fill the distance matrix with the three loops in the right order
  • State the recurrence in terms of allowed intermediate vertices
  • Detect vertices on a negative cycle
  • Compute the transitive closure with the same pattern

Prerequisites

Shortest path frameworkDynamic programming basics

Sometimes you need the answer for every pair: a distance table between cities, the graph's diameter, or which stations reach which. For a few hundred vertices a three-line algorithm is plenty.

35.06.1

All-pairs DP

Store the matrix d[i][j]: infinity at first, 0 on the diagonal, and the edge weight (the lightest if there are parallel edges) where an edge exists. For each vertex k in turn, and for every pair (i, j), try the route i → k → j: if d[i][k] + d[k][j] < d[i][j], update. The result is the distance for every pair.

It takes O(n³) time and O(n²) space regardless of the number of edges, so it suits dense graphs or small n. Step through the animation: each improved cell lights up, and row k and column k are marked as the new intermediate vertex.

Java
1static long[][] floyd(int n, int[][] edges) {                    // edges {u, v, w}; null when a negative cycle exists
2    long INF = Long.MAX_VALUE / 4;
3    long[][] d = new long[n][n];
4    for (long[] r : d) Arrays.fill(r, INF);
5    for (int i = 0; i < n; i++) d[i][i] = 0;
6    for (int[] e : edges) d[e[0]][e[1]] = Math.min(d[e[0]][e[1]], e[2]);
7    for (int k = 0; k < n; k++)                                   // k must be the outermost loop
8        for (int i = 0; i < n; i++)
9            for (int j = 0; j < n; j++)
10                if (d[i][k] < INF && d[k][j] < INF && d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j];
11    for (int i = 0; i < n; i++) if (d[i][i] < 0) return null;
12    return d;
13}

Floyd-Warshall: all-pairs shortest paths and transitive closure

Interactive · edit the input

Your input

Try

grid · 5 × 5

01234
0
0
1
2
3
1
0
0
3
∞
7
2
1
∞
0
-2
∞
3
2
∞
∞
0
2
4
3
∞
1
∞
0
Cell just improvedRow k and column k (the new intermediate vertex)Known value
Setup

d[i][j] is the cheapest known cost from i to j using no intermediate vertices: the arrow weight (lightest if parallel), 0 on the diagonal, ∞ otherwise. Each round k allows vertex k as an intermediate stop.

Step 1 / 11
Java
1long[][] floydWarshall(int n, int[][] edges) {    // edges: {u, v, w}; null when a negative cycle exists
2    long INF = Long.MAX_VALUE / 4;
3    long[][] d = new long[n][n];
4    for (long[] r : d) Arrays.fill(r, INF);
5    for (int i = 0; i < n; i++) d[i][i] = 0;
6    for (int[] e : edges) d[e[0]][e[1]] = Math.min(d[e[0]][e[1]], e[2]);   // keep the lightest parallel edge
7    for (int k = 0; k < n; k++)                   // intermediate vertices allowed so far: 0..k
8        for (int i = 0; i < n; i++)
9            for (int j = 0; j < n; j++)
10                if (d[i][k] < INF && d[k][j] < INF && d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j];
11    for (int i = 0; i < n; i++) if (d[i][i] < 0) return null;   // a vertex that returns to itself with negative cost
12    return d;
13}

Live state

0 improvements

n

4

No condition evaluated on this step
Execution trace (dry run table)Show 11 steps
StepLineStateWhat happens
1L3n=4d[i][j] is the cheapest known cost from i to j using no intermediate vertices: the arrow weight (lightest if parallel), 0 on the diagonal, ∞ otherwise. Each round k allows vertex k as an intermediate stop.
2L7k=0Round 0: going through 0 changes nothing.
3L9k=1 i=0 j=2 d[i][j]=1Through 1: d[0][1] + d[1][2] = 3 + -2 = 1, better than the old d[0][2]. Update it.
4L9k=1 i=3 j=2 d[i][j]=-1Through 1: d[3][1] + d[1][2] = 1 + -2 = -1, better than the old d[3][2]. Update it.
5L7k=1Round 1 done: some distances improved by going through 1. Intermediate vertices 0..1 are now allowed.
6L9k=2 i=0 j=3 d[i][j]=3Through 2: d[0][2] + d[2][3] = 1 + 2 = 3, better than the old d[0][3]. Update it.
7L9k=2 i=1 j=3 d[i][j]=0Through 2: d[1][2] + d[2][3] = -2 + 2 = 0, better than the old d[1][3]. Update it.
8L7k=2Round 2 done: some distances improved by going through 2. Intermediate vertices 0..2 are now allowed.
9L9k=3 i=2 j=1 d[i][j]=3Through 3: d[2][3] + d[3][1] = 2 + 1 = 3, better than the old d[2][1]. Update it.
10L7k=3Round 3 done: some distances improved by going through 3. Intermediate vertices 0..3 are now allowed.
11L12return=[0, 3, 1, 3] | [-, 0, -2, 0] | [-, 3, 0, 2] | [-, 1, -1, 0] improvements=5The diagonal is all zeros, so there is no negative cycle. Row i holds the shortest distance from i to every vertex ('∞' = unreachable). Three nested loops: O(n³) time, O(n²) space.
35.06.2

Intermediate-vertex recurrence

Let d_k[i][j] be the cheapest i → j path that uses only vertices 0 .. k - 1 as intermediate stops. Such a path either avoids vertex k or passes through it once, so d_{k+1}[i][j] = min(d_k[i][j], d_k[i][k] + d_k[k][j]). The base is d_0 = the direct edge weights. The program keeps just one matrix because round k never changes row k or column k (when there is no negative cycle), so the update is safe in place.

The recurrence is why the loop order matters: k is the outer loop, because each round must finish a whole matrix before the next vertex is allowed. The code keeps every layer so the idea is visible.

Java
1static long[][][] floydLayers(int n, int[][] edges) {            // layers[k][i][j]: cheapest i -> j using only intermediate vertices 0..k-1
2    long INF = Long.MAX_VALUE / 4;
3    long[][][] layers = new long[n + 1][n][n];
4    for (long[][] m : layers) for (long[] r : m) Arrays.fill(r, INF);
5    for (int i = 0; i < n; i++) layers[0][i][i] = 0;
6    for (int[] e : edges) layers[0][e[0]][e[1]] = Math.min(layers[0][e[0]][e[1]], e[2]);
7    for (int k = 0; k < n; k++)
8        for (int i = 0; i < n; i++)
9            for (int j = 0; j < n; j++) {
10                long keep = layers[k][i][j];
11                long through = layers[k][i][k] < INF && layers[k][k][j] < INF ? layers[k][i][k] + layers[k][k][j] : INF;
12                layers[k + 1][i][j] = Math.min(keep, through);   // avoid vertex k, or pass through it once
13            }
14    return layers;
15}

Floyd-Warshall: all-pairs shortest paths and transitive closure

Interactive · edit the input

Your input

Try

grid · 5 × 5

01234
0
0
1
2
3
1
0
0
3
∞
7
2
1
∞
0
-2
∞
3
2
∞
∞
0
2
4
3
∞
1
∞
0
Cell just improvedRow k and column k (the new intermediate vertex)Known value
Setup

d[i][j] is the cheapest known cost from i to j using no intermediate vertices: the arrow weight (lightest if parallel), 0 on the diagonal, ∞ otherwise. Each round k allows vertex k as an intermediate stop.

Step 1 / 11
Java
1long[][] floydWarshall(int n, int[][] edges) {    // edges: {u, v, w}; null when a negative cycle exists
2    long INF = Long.MAX_VALUE / 4;
3    long[][] d = new long[n][n];
4    for (long[] r : d) Arrays.fill(r, INF);
5    for (int i = 0; i < n; i++) d[i][i] = 0;
6    for (int[] e : edges) d[e[0]][e[1]] = Math.min(d[e[0]][e[1]], e[2]);   // keep the lightest parallel edge
7    for (int k = 0; k < n; k++)                   // intermediate vertices allowed so far: 0..k
8        for (int i = 0; i < n; i++)
9            for (int j = 0; j < n; j++)
10                if (d[i][k] < INF && d[k][j] < INF && d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j];
11    for (int i = 0; i < n; i++) if (d[i][i] < 0) return null;   // a vertex that returns to itself with negative cost
12    return d;
13}

Live state

0 improvements

n

4

No condition evaluated on this step
Execution trace (dry run table)Show 11 steps
StepLineStateWhat happens
1L3n=4d[i][j] is the cheapest known cost from i to j using no intermediate vertices: the arrow weight (lightest if parallel), 0 on the diagonal, ∞ otherwise. Each round k allows vertex k as an intermediate stop.
2L7k=0Round 0: going through 0 changes nothing.
3L9k=1 i=0 j=2 d[i][j]=1Through 1: d[0][1] + d[1][2] = 3 + -2 = 1, better than the old d[0][2]. Update it.
4L9k=1 i=3 j=2 d[i][j]=-1Through 1: d[3][1] + d[1][2] = 1 + -2 = -1, better than the old d[3][2]. Update it.
5L7k=1Round 1 done: some distances improved by going through 1. Intermediate vertices 0..1 are now allowed.
6L9k=2 i=0 j=3 d[i][j]=3Through 2: d[0][2] + d[2][3] = 1 + 2 = 3, better than the old d[0][3]. Update it.
7L9k=2 i=1 j=3 d[i][j]=0Through 2: d[1][2] + d[2][3] = -2 + 2 = 0, better than the old d[1][3]. Update it.
8L7k=2Round 2 done: some distances improved by going through 2. Intermediate vertices 0..2 are now allowed.
9L9k=3 i=2 j=1 d[i][j]=3Through 3: d[2][3] + d[3][1] = 2 + 1 = 3, better than the old d[2][1]. Update it.
10L7k=3Round 3 done: some distances improved by going through 3. Intermediate vertices 0..3 are now allowed.
11L12return=[0, 3, 1, 3] | [-, 0, -2, 0] | [-, 3, 0, 2] | [-, 1, -1, 0] improvements=5The diagonal is all zeros, so there is no negative cycle. Row i holds the shortest distance from i to every vertex ('∞' = unreachable). Three nested loops: O(n³) time, O(n²) space.
35.06.3

Negative cycles

If d[i][i] becomes negative, vertex i can leave and come back with negative total cost: it lies on a negative closed walk. After the loops, every vertex on a negative cycle has a negative diagonal entry, and a negative entry always means such a closed walk exists. A pair (i, j) whose paths can pass through a negative cycle has no finite shortest distance.

With a negative cycle, numbers can shrink exponentially during the loops, so a robust implementation clamps values at a large negative bound to avoid overflow. The *Negative cycle shows on the diagonal* preset reports d[0][0] = -1.

Java
1static boolean[] onNegativeCycle(int n, int[][] edges) {         // vertices on a negative closed walk
2    long INF = Long.MAX_VALUE / 4;
3    long[][] d = new long[n][n];
4    for (long[] r : d) Arrays.fill(r, INF);
5    for (int i = 0; i < n; i++) d[i][i] = 0;
6    for (int[] e : edges) d[e[0]][e[1]] = Math.min(d[e[0]][e[1]], e[2]);
7    for (int k = 0; k < n; k++)
8        for (int i = 0; i < n; i++)
9            for (int j = 0; j < n; j++)
10                if (d[i][k] < INF && d[k][j] < INF) d[i][j] = Math.max(-INF, Math.min(d[i][j], d[i][k] + d[k][j]));   // clamp: no overflow
11    boolean[] bad = new boolean[n];
12    for (int i = 0; i < n; i++) bad[i] = d[i][i] < 0;
13    return bad;
14}

Floyd-Warshall: all-pairs shortest paths and transitive closure

Interactive · edit the input

Your input

Try

grid · 5 × 5

01234
0
0
1
2
3
1
0
0
3
∞
7
2
1
∞
0
-2
∞
3
2
∞
∞
0
2
4
3
∞
1
∞
0
Cell just improvedRow k and column k (the new intermediate vertex)Known value
Setup

d[i][j] is the cheapest known cost from i to j using no intermediate vertices: the arrow weight (lightest if parallel), 0 on the diagonal, ∞ otherwise. Each round k allows vertex k as an intermediate stop.

Step 1 / 11
Java
1long[][] floydWarshall(int n, int[][] edges) {    // edges: {u, v, w}; null when a negative cycle exists
2    long INF = Long.MAX_VALUE / 4;
3    long[][] d = new long[n][n];
4    for (long[] r : d) Arrays.fill(r, INF);
5    for (int i = 0; i < n; i++) d[i][i] = 0;
6    for (int[] e : edges) d[e[0]][e[1]] = Math.min(d[e[0]][e[1]], e[2]);   // keep the lightest parallel edge
7    for (int k = 0; k < n; k++)                   // intermediate vertices allowed so far: 0..k
8        for (int i = 0; i < n; i++)
9            for (int j = 0; j < n; j++)
10                if (d[i][k] < INF && d[k][j] < INF && d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j];
11    for (int i = 0; i < n; i++) if (d[i][i] < 0) return null;   // a vertex that returns to itself with negative cost
12    return d;
13}

Live state

0 improvements

n

4

No condition evaluated on this step
Execution trace (dry run table)Show 11 steps
StepLineStateWhat happens
1L3n=4d[i][j] is the cheapest known cost from i to j using no intermediate vertices: the arrow weight (lightest if parallel), 0 on the diagonal, ∞ otherwise. Each round k allows vertex k as an intermediate stop.
2L7k=0Round 0: going through 0 changes nothing.
3L9k=1 i=0 j=2 d[i][j]=1Through 1: d[0][1] + d[1][2] = 3 + -2 = 1, better than the old d[0][2]. Update it.
4L9k=1 i=3 j=2 d[i][j]=-1Through 1: d[3][1] + d[1][2] = 1 + -2 = -1, better than the old d[3][2]. Update it.
5L7k=1Round 1 done: some distances improved by going through 1. Intermediate vertices 0..1 are now allowed.
6L9k=2 i=0 j=3 d[i][j]=3Through 2: d[0][2] + d[2][3] = 1 + 2 = 3, better than the old d[0][3]. Update it.
7L9k=2 i=1 j=3 d[i][j]=0Through 2: d[1][2] + d[2][3] = -2 + 2 = 0, better than the old d[1][3]. Update it.
8L7k=2Round 2 done: some distances improved by going through 2. Intermediate vertices 0..2 are now allowed.
9L9k=3 i=2 j=1 d[i][j]=3Through 3: d[2][3] + d[3][1] = 2 + 1 = 3, better than the old d[2][1]. Update it.
10L7k=3Round 3 done: some distances improved by going through 3. Intermediate vertices 0..3 are now allowed.
11L12return=[0, 3, 1, 3] | [-, 0, -2, 0] | [-, 3, 0, 2] | [-, 1, -1, 0] improvements=5The diagonal is all zeros, so there is no negative cycle. Row i holds the shortest distance from i to every vertex ('∞' = unreachable). Three nested loops: O(n³) time, O(n²) space.
35.06.4

Transitive closure

Replace distances with booleans and +/min with and/or: reach[i][j] |= reach[i][k] && reach[k][j]. This is **Warshall's algorithm**; Floyd's shortest-path version is the same loops with a different operation. After round k, reach[i][j] says whether a path exists through intermediate vertices 0..k.

With bitsets the inner j loop becomes one word-wise OR: reach[i].or(reach[k]) whenever i reaches k, giving O(n³ / 64). Switch the animation to *Transitive closure* to see 1 and 0 instead of distances.

Java
1static BitSet[] closureBits(int n, int[][] edges) {              // reach[i].get(j): there is a path from i to j (every vertex reaches itself)
2    BitSet[] reach = new BitSet[n];
3    for (int i = 0; i < n; i++) { reach[i] = new BitSet(n); reach[i].set(i); }
4    for (int[] e : edges) reach[e[0]].set(e[1]);
5    for (int k = 0; k < n; k++)
6        for (int i = 0; i < n; i++)
7            if (reach[i].get(k)) reach[i].or(reach[k]);          // one OR replaces the loop over j
8    return reach;
9}

Floyd-Warshall: all-pairs shortest paths and transitive closure

Interactive · edit the input

Your input

Try

grid · 5 × 5

01234
0
0
1
2
3
1
0
0
3
∞
7
2
1
∞
0
-2
∞
3
2
∞
∞
0
2
4
3
∞
1
∞
0
Cell just improvedRow k and column k (the new intermediate vertex)Known value
Setup

d[i][j] is the cheapest known cost from i to j using no intermediate vertices: the arrow weight (lightest if parallel), 0 on the diagonal, ∞ otherwise. Each round k allows vertex k as an intermediate stop.

Step 1 / 11
Java
1long[][] floydWarshall(int n, int[][] edges) {    // edges: {u, v, w}; null when a negative cycle exists
2    long INF = Long.MAX_VALUE / 4;
3    long[][] d = new long[n][n];
4    for (long[] r : d) Arrays.fill(r, INF);
5    for (int i = 0; i < n; i++) d[i][i] = 0;
6    for (int[] e : edges) d[e[0]][e[1]] = Math.min(d[e[0]][e[1]], e[2]);   // keep the lightest parallel edge
7    for (int k = 0; k < n; k++)                   // intermediate vertices allowed so far: 0..k
8        for (int i = 0; i < n; i++)
9            for (int j = 0; j < n; j++)
10                if (d[i][k] < INF && d[k][j] < INF && d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j];
11    for (int i = 0; i < n; i++) if (d[i][i] < 0) return null;   // a vertex that returns to itself with negative cost
12    return d;
13}

Live state

0 improvements

n

4

No condition evaluated on this step
Execution trace (dry run table)Show 11 steps
StepLineStateWhat happens
1L3n=4d[i][j] is the cheapest known cost from i to j using no intermediate vertices: the arrow weight (lightest if parallel), 0 on the diagonal, ∞ otherwise. Each round k allows vertex k as an intermediate stop.
2L7k=0Round 0: going through 0 changes nothing.
3L9k=1 i=0 j=2 d[i][j]=1Through 1: d[0][1] + d[1][2] = 3 + -2 = 1, better than the old d[0][2]. Update it.
4L9k=1 i=3 j=2 d[i][j]=-1Through 1: d[3][1] + d[1][2] = 1 + -2 = -1, better than the old d[3][2]. Update it.
5L7k=1Round 1 done: some distances improved by going through 1. Intermediate vertices 0..1 are now allowed.
6L9k=2 i=0 j=3 d[i][j]=3Through 2: d[0][2] + d[2][3] = 1 + 2 = 3, better than the old d[0][3]. Update it.
7L9k=2 i=1 j=3 d[i][j]=0Through 2: d[1][2] + d[2][3] = -2 + 2 = 0, better than the old d[1][3]. Update it.
8L7k=2Round 2 done: some distances improved by going through 2. Intermediate vertices 0..2 are now allowed.
9L9k=3 i=2 j=1 d[i][j]=3Through 3: d[2][3] + d[3][1] = 2 + 1 = 3, better than the old d[2][1]. Update it.
10L7k=3Round 3 done: some distances improved by going through 3. Intermediate vertices 0..3 are now allowed.
11L12return=[0, 3, 1, 3] | [-, 0, -2, 0] | [-, 3, 0, 2] | [-, 1, -1, 0] improvements=5The diagonal is all zeros, so there is no negative cycle. Row i holds the shortest distance from i to every vertex ('∞' = unreachable). Three nested loops: O(n³) time, O(n²) space.

Practice ladder

Now try it yourself

Easy

  • Network Delay Time

Medium

  • Find the City With the Smallest Number of Neighbors at a Threshold Distance
  • Course Schedule IV

Advanced

  • Shortest Path Visiting All Nodes
  • Minimum Weighted Subgraph With the Required Paths

Key takeaways

  • Floyd-Warshall: for each k, for each pair, try the route through k; O(n³) time, O(n²) space.
  • The recurrence allows intermediate vertices 0..k; k must be the outer loop.
  • A negative value on the diagonal marks a vertex on a negative cycle; clamp values to avoid overflow.
  • The same loops with boolean operations give the transitive closure, fast with bitsets.