35.07Intermediate / Advanced3 topics14 min3 interactive animations

Johnson's algorithm

Johnson's algorithm finds all-pairs shortest paths in a sparse graph with negative edges: Bellman-Ford computes potentials that reweight every edge to be non-negative, then Dijkstra runs from every vertex.

Learning goals

Compute the potentials with Bellman-Ford from a virtual source
Reweight edges so none is negative and shortest paths are unchanged
Run Dijkstra from each vertex and undo the shift
Choose between Johnson and Floyd-Warshall

Prerequisites

Bellman-FordDijkstra's algorithm

With negative edges you cannot run Dijkstra from every vertex, and Floyd-Warshall costs n³ even when the graph is sparse. Johnson's trick is to change the weights, without changing which paths are shortest, so that Dijkstra becomes legal.

35.07.1

Reweighting potentials

Give every vertex a number h[v], its **potential**, and replace each edge weight by w'(u, v) = w(u, v) + h[u] - h[v]. A path s → t then costs h[s] - h[t] more (or less) than before: the middle terms cancel. That shift depends only on the two ends, so the shortest path between two given vertices is unchanged.

Choose h as shortest distances from a virtual source joined to every vertex by a 0-weight edge, found with Bellman-Ford. Then h[v] <= h[u] + w(u, v) holds for every edge, which says exactly that every w' is non-negative. If Bellman-Ford finds a negative cycle, the algorithm stops: there are no shortest paths.

Java

1static long[] potentials(int n, int[][] edges) {                  // null on a negative cycle
2    long[] h = new long[n];                                       // Bellman-Ford from a virtual source joined to every vertex by weight 0
3    for (int round = 0; round < n; round++) {
4        boolean changed = false;
5        for (int[] e : edges)
6            if (h[e[0]] + e[2] < h[e[1]]) { h[e[1]] = h[e[0]] + e[2]; changed = true; }
7        if (!changed) return h;
8    }
9    return null;
10}
11static int[][] reweight(int[][] edges, long[] h) {                // w' = w + h[u] - h[v], never negative
12    int[][] out = new int[edges.length][];
13    for (int i = 0; i < edges.length; i++)
14        out[i] = new int[]{edges[i][0], edges[i][1], (int) (edges[i][2] + h[edges[i][0]] - h[edges[i][1]])};
15    return out;
16}

Johnson's algorithm: Bellman-Ford potentials, reweighting, Dijkstra from every vertex

Interactive · edit the input

directed graph · 4 vertices · 5 edges

h=0

Source being processedReweighted edge (never negative)Still improving: negative cycle

h[v] (potential)

Setup

Dijkstra needs non-negative weights. Johnson fixes that first: add a virtual source with 0-weight edges to every vertex and run Bellman-Ford. The resulting distances h[v] are potentials with h[v] <= h[u] + w for every edge u → v. All h start at 0 (the first edges of those paths).

Step 1 / 9

Java

1long[][] johnson(int n, int[][] edges) {          // null on a negative cycle
2    long INF = Long.MAX_VALUE / 4;
3    long[] h = new long[n];                       // potentials: Bellman-Ford from a virtual source joined to every vertex by weight 0
4    for (int round = 0; round < n; round++) {
5        boolean changed = false;
6        for (int[] e : edges) if (h[e[0]] + e[2] < h[e[1]]) { h[e[1]] = h[e[0]] + e[2]; changed = true; }
7        if (!changed) break;
8        if (round == n - 1) return null;          // still improving after n rounds: a negative cycle
9    }
10    List<int[]>[] adj = new List[n];
11    for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
12    for (int[] e : edges) adj[e[0]].add(new int[]{e[1], (int) (e[2] + h[e[0]] - h[e[1]])});   // never negative
13    long[][] d = new long[n][];
14    for (int s = 0; s < n; s++) {
15        long[] ds = dijkstra(n, adj, s);
16        d[s] = new long[n];
17        for (int v = 0; v < n; v++) d[s][v] = ds[v] >= INF ? INF : ds[v] - h[s] + h[v];   // undo the reweighting
18    }
19    return d;
20}
21long[] dijkstra(int n, List<int[]>[] adj, int s) {
22    long INF = Long.MAX_VALUE / 4;
23    long[] dist = new long[n]; Arrays.fill(dist, INF); dist[s] = 0;
24    PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
25    pq.add(new long[]{0, s});
26    while (!pq.isEmpty()) {
27        long[] top = pq.poll(); int u = (int) top[1];
28        if (top[0] > dist[u]) continue;
29        for (int[] e : adj[u]) if (dist[u] + e[1] < dist[e[0]]) { dist[e[0]] = dist[u] + e[1]; pq.add(new long[]{dist[e[0]], e[0]}); }
30    }
31    return dist;
32}

Live state

0 Bellman-Ford rounds0 Dijkstra runs

No condition evaluated on this step

Execution trace (dry run table)Show 9 steps

Step	Line	State	What happens
1	L3	n=4	Dijkstra needs non-negative weights. Johnson fixes that first: add a virtual source with 0-weight edges to every vertex and run Bellman-Ford. The resulting distances h[v] are potentials with h[v] <= h[u] + w for every edge u → v. All h start at 0 (the first edges of those paths).
2	L5	round=1 h=[0, 0, -2, 0]	Bellman-Ford round 1: h = [0, 0, -2, 0].
3	L5	round=2 h=[0, 0, -2, 0]	Bellman-Ford round 2: h = [0, 0, -2, 0] (nothing changed: done).
4	L12	reweighted=[3, 0, 0, 7, 1]	Reweight each edge: w' = w + h[u] - h[v]. The new weights [3, 0, 0, 7, 1] are all >= 0 because h[v] <= h[u] + w. Every path from s to t changes by the same amount h[s] - h[t], so shortest paths stay shortest.
5	L15	source=0	Dijkstra from 0 on the reweighted graph gives [0, 3, 3, 3]. Undo the shift with d(0, v) = d'(0, v) - h[0] + h[v]: [0, 3, 1, 3].
6	L15	source=1	Dijkstra from 1 on the reweighted graph gives [∞, 0, 0, 0]. Undo the shift with d(1, v) = d'(1, v) - h[1] + h[v]: [∞, 0, -2, 0].
7	L15	source=2	Dijkstra from 2 on the reweighted graph gives [∞, 1, 0, 0]. Undo the shift with d(2, v) = d'(2, v) - h[2] + h[v]: [∞, 3, 0, 2].
8	L15	source=3	Dijkstra from 3 on the reweighted graph gives [∞, 1, 1, 0]. Undo the shift with d(3, v) = d'(3, v) - h[3] + h[v]: [∞, 1, -1, 0].
9	L19	return=[0, 3, 1, 3] \| [-, 0, -2, 0] \| [-, 3, 0, 2] \| [-, 1, -1, 0]	All-pairs distances (rows are sources, '∞' = unreachable). The cost is one Bellman-Ford O(n · m) plus n Dijkstra runs O(n · m log n): better than Floyd-Warshall's O(n³) when the graph is sparse.

35.07.2

Bellman-Ford + Dijkstra

The algorithm in order: (1) compute the potentials with Bellman-Ford, (2) reweight all edges, (3) run Dijkstra from each source on the reweighted graph, (4) convert each distance back with d(s, v) = d'(s, v) - h[s] + h[v]. The animation shows each step, including the reweighted labels w -> w' and the distances before and after the conversion.

The cost is one Bellman-Ford O(n · m) plus n runs of Dijkstra O(n · m log n) with a binary heap. Unreachable pairs stay unreachable.

Java

1static long[][] johnson(int n, int[][] edges) {                   // null on a negative cycle; Long.MAX_VALUE / 4 = unreachable
2    long INF = Long.MAX_VALUE / 4;
3    long[] h = new long[n];
4    for (int round = 0; round < n; round++) {
5        boolean changed = false;
6        for (int[] e : edges) if (h[e[0]] + e[2] < h[e[1]]) { h[e[1]] = h[e[0]] + e[2]; changed = true; }
7        if (!changed) break;
8        if (round == n - 1) return null;
9    }
10    List<int[]>[] adj = new List[n];
11    for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
12    for (int[] e : edges) adj[e[0]].add(new int[]{e[1], (int) (e[2] + h[e[0]] - h[e[1]])});
13    long[][] d = new long[n][];
14    for (int s = 0; s < n; s++) {
15        long[] ds = dijkstra(n, adj, s);
16        d[s] = new long[n];
17        for (int v = 0; v < n; v++) d[s][v] = ds[v] >= INF ? INF : ds[v] - h[s] + h[v];
18    }
19    return d;
20}
21static long[] dijkstra(int n, List<int[]>[] adj, int s) {
22    long INF = Long.MAX_VALUE / 4;
23    long[] dist = new long[n];
24    Arrays.fill(dist, INF);
25    dist[s] = 0;
26    PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
27    pq.add(new long[]{0, s});
28    while (!pq.isEmpty()) {
29        long[] top = pq.poll();
30        int u = (int) top[1];
31        if (top[0] > dist[u]) continue;
32        for (int[] e : adj[u])
33            if (dist[u] + e[1] < dist[e[0]]) { dist[e[0]] = dist[u] + e[1]; pq.add(new long[]{dist[e[0]], e[0]}); }
34    }
35    return dist;
36}

Johnson's algorithm: Bellman-Ford potentials, reweighting, Dijkstra from every vertex

Interactive · edit the input

directed graph · 4 vertices · 5 edges

h=0

Source being processedReweighted edge (never negative)Still improving: negative cycle

h[v] (potential)

Setup

Step 1 / 9

Java

1long[][] johnson(int n, int[][] edges) {          // null on a negative cycle
2    long INF = Long.MAX_VALUE / 4;
3    long[] h = new long[n];                       // potentials: Bellman-Ford from a virtual source joined to every vertex by weight 0
4    for (int round = 0; round < n; round++) {
5        boolean changed = false;
6        for (int[] e : edges) if (h[e[0]] + e[2] < h[e[1]]) { h[e[1]] = h[e[0]] + e[2]; changed = true; }
7        if (!changed) break;
8        if (round == n - 1) return null;          // still improving after n rounds: a negative cycle
9    }
10    List<int[]>[] adj = new List[n];
11    for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
12    for (int[] e : edges) adj[e[0]].add(new int[]{e[1], (int) (e[2] + h[e[0]] - h[e[1]])});   // never negative
13    long[][] d = new long[n][];
14    for (int s = 0; s < n; s++) {
15        long[] ds = dijkstra(n, adj, s);
16        d[s] = new long[n];
17        for (int v = 0; v < n; v++) d[s][v] = ds[v] >= INF ? INF : ds[v] - h[s] + h[v];   // undo the reweighting
18    }
19    return d;
20}
21long[] dijkstra(int n, List<int[]>[] adj, int s) {
22    long INF = Long.MAX_VALUE / 4;
23    long[] dist = new long[n]; Arrays.fill(dist, INF); dist[s] = 0;
24    PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
25    pq.add(new long[]{0, s});
26    while (!pq.isEmpty()) {
27        long[] top = pq.poll(); int u = (int) top[1];
28        if (top[0] > dist[u]) continue;
29        for (int[] e : adj[u]) if (dist[u] + e[1] < dist[e[0]]) { dist[e[0]] = dist[u] + e[1]; pq.add(new long[]{dist[e[0]], e[0]}); }
30    }
31    return dist;
32}

Live state

0 Bellman-Ford rounds0 Dijkstra runs

No condition evaluated on this step

Execution trace (dry run table)Show 9 steps

Step	Line	State	What happens
1	L3	n=4	Dijkstra needs non-negative weights. Johnson fixes that first: add a virtual source with 0-weight edges to every vertex and run Bellman-Ford. The resulting distances h[v] are potentials with h[v] <= h[u] + w for every edge u → v. All h start at 0 (the first edges of those paths).
2	L5	round=1 h=[0, 0, -2, 0]	Bellman-Ford round 1: h = [0, 0, -2, 0].
3	L5	round=2 h=[0, 0, -2, 0]	Bellman-Ford round 2: h = [0, 0, -2, 0] (nothing changed: done).
4	L12	reweighted=[3, 0, 0, 7, 1]	Reweight each edge: w' = w + h[u] - h[v]. The new weights [3, 0, 0, 7, 1] are all >= 0 because h[v] <= h[u] + w. Every path from s to t changes by the same amount h[s] - h[t], so shortest paths stay shortest.
5	L15	source=0	Dijkstra from 0 on the reweighted graph gives [0, 3, 3, 3]. Undo the shift with d(0, v) = d'(0, v) - h[0] + h[v]: [0, 3, 1, 3].
6	L15	source=1	Dijkstra from 1 on the reweighted graph gives [∞, 0, 0, 0]. Undo the shift with d(1, v) = d'(1, v) - h[1] + h[v]: [∞, 0, -2, 0].
7	L15	source=2	Dijkstra from 2 on the reweighted graph gives [∞, 1, 0, 0]. Undo the shift with d(2, v) = d'(2, v) - h[2] + h[v]: [∞, 3, 0, 2].
8	L15	source=3	Dijkstra from 3 on the reweighted graph gives [∞, 1, 1, 0]. Undo the shift with d(3, v) = d'(3, v) - h[3] + h[v]: [∞, 1, -1, 0].
9	L19	return=[0, 3, 1, 3] \| [-, 0, -2, 0] \| [-, 3, 0, 2] \| [-, 1, -1, 0]	All-pairs distances (rows are sources, '∞' = unreachable). The cost is one Bellman-Ford O(n · m) plus n Dijkstra runs O(n · m log n): better than Floyd-Warshall's O(n³) when the graph is sparse.

35.07.3

Sparse all-pairs shortest paths

Floyd-Warshall costs about n³ regardless of edges. Johnson costs about n · (n + m) log n plus the Bellman-Ford pass, which is much smaller when m is far below n². For a dense graph (m close to n²) the two are close, and Floyd-Warshall's simple loops usually win in practice.

If all weights are already non-negative, skip the potentials and run Dijkstra from every vertex. The helper below compares rough operation counts; treat the result as a guide, not a measurement, since constants differ.

Java

1static String chooseAllPairs(int n, int m, boolean hasNegativeEdges) {   // compares rough operation counts
2    double log = Math.log(Math.max(n, 2)) / Math.log(2);
3    double floyd = (double) n * n * n;
4    double repeated = (double) n * (m + n) * log;                         // n heap-based Dijkstra runs
5    if (hasNegativeEdges) repeated += (double) n * m;                     // plus one Bellman-Ford for the potentials
6    if (floyd <= repeated) return "Floyd-Warshall";
7    return hasNegativeEdges ? "Johnson" : "Dijkstra from every vertex";
8}

Johnson's algorithm: Bellman-Ford potentials, reweighting, Dijkstra from every vertex

Interactive · edit the input

directed graph · 4 vertices · 5 edges

h=0

Source being processedReweighted edge (never negative)Still improving: negative cycle

h[v] (potential)

Setup

Step 1 / 9

Java

1long[][] johnson(int n, int[][] edges) {          // null on a negative cycle
2    long INF = Long.MAX_VALUE / 4;
3    long[] h = new long[n];                       // potentials: Bellman-Ford from a virtual source joined to every vertex by weight 0
4    for (int round = 0; round < n; round++) {
5        boolean changed = false;
6        for (int[] e : edges) if (h[e[0]] + e[2] < h[e[1]]) { h[e[1]] = h[e[0]] + e[2]; changed = true; }
7        if (!changed) break;
8        if (round == n - 1) return null;          // still improving after n rounds: a negative cycle
9    }
10    List<int[]>[] adj = new List[n];
11    for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
12    for (int[] e : edges) adj[e[0]].add(new int[]{e[1], (int) (e[2] + h[e[0]] - h[e[1]])});   // never negative
13    long[][] d = new long[n][];
14    for (int s = 0; s < n; s++) {
15        long[] ds = dijkstra(n, adj, s);
16        d[s] = new long[n];
17        for (int v = 0; v < n; v++) d[s][v] = ds[v] >= INF ? INF : ds[v] - h[s] + h[v];   // undo the reweighting
18    }
19    return d;
20}
21long[] dijkstra(int n, List<int[]>[] adj, int s) {
22    long INF = Long.MAX_VALUE / 4;
23    long[] dist = new long[n]; Arrays.fill(dist, INF); dist[s] = 0;
24    PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
25    pq.add(new long[]{0, s});
26    while (!pq.isEmpty()) {
27        long[] top = pq.poll(); int u = (int) top[1];
28        if (top[0] > dist[u]) continue;
29        for (int[] e : adj[u]) if (dist[u] + e[1] < dist[e[0]]) { dist[e[0]] = dist[u] + e[1]; pq.add(new long[]{dist[e[0]], e[0]}); }
30    }
31    return dist;
32}

Live state

0 Bellman-Ford rounds0 Dijkstra runs

No condition evaluated on this step

Execution trace (dry run table)Show 9 steps

Step	Line	State	What happens
1	L3	n=4	Dijkstra needs non-negative weights. Johnson fixes that first: add a virtual source with 0-weight edges to every vertex and run Bellman-Ford. The resulting distances h[v] are potentials with h[v] <= h[u] + w for every edge u → v. All h start at 0 (the first edges of those paths).
2	L5	round=1 h=[0, 0, -2, 0]	Bellman-Ford round 1: h = [0, 0, -2, 0].
3	L5	round=2 h=[0, 0, -2, 0]	Bellman-Ford round 2: h = [0, 0, -2, 0] (nothing changed: done).
4	L12	reweighted=[3, 0, 0, 7, 1]	Reweight each edge: w' = w + h[u] - h[v]. The new weights [3, 0, 0, 7, 1] are all >= 0 because h[v] <= h[u] + w. Every path from s to t changes by the same amount h[s] - h[t], so shortest paths stay shortest.
5	L15	source=0	Dijkstra from 0 on the reweighted graph gives [0, 3, 3, 3]. Undo the shift with d(0, v) = d'(0, v) - h[0] + h[v]: [0, 3, 1, 3].
6	L15	source=1	Dijkstra from 1 on the reweighted graph gives [∞, 0, 0, 0]. Undo the shift with d(1, v) = d'(1, v) - h[1] + h[v]: [∞, 0, -2, 0].
7	L15	source=2	Dijkstra from 2 on the reweighted graph gives [∞, 1, 0, 0]. Undo the shift with d(2, v) = d'(2, v) - h[2] + h[v]: [∞, 3, 0, 2].
8	L15	source=3	Dijkstra from 3 on the reweighted graph gives [∞, 1, 1, 0]. Undo the shift with d(3, v) = d'(3, v) - h[3] + h[v]: [∞, 1, -1, 0].
9	L19	return=[0, 3, 1, 3] \| [-, 0, -2, 0] \| [-, 3, 0, 2] \| [-, 1, -1, 0]	All-pairs distances (rows are sources, '∞' = unreachable). The cost is one Bellman-Ford O(n · m) plus n Dijkstra runs O(n · m log n): better than Floyd-Warshall's O(n³) when the graph is sparse.

Practice ladder

Now try it yourself

Easy

Network Delay Time

Medium

Find the City With the Smallest Number of Neighbors at a Threshold Distance

Advanced

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

Key takeaways

Potentials h[v] from Bellman-Ford make w' = w + h[u] - h[v] non-negative.
Every s-to-t path shifts by h[s] - h[t], so shortest paths do not change.
Run Dijkstra from each vertex, then convert back with d = d' - h[s] + h[t].
Johnson beats Floyd-Warshall on sparse graphs; Floyd-Warshall is simpler on dense ones.