10.16 Solving Sparse All-Pairs Shortest Paths with Johnson's Algorithm

The shortest-path algorithms studied so far naturally divide into two groups.

Single-source algorithms:

BFS
Dijkstra
Bellman-Ford
DAG shortest paths
A*

All-pairs algorithms:

Floyd-Warshall

When a graph contains thousands or millions of vertices, Floyd-Warshall's cubic running time often becomes impractical. Running Dijkstra from every vertex can be much faster for sparse graphs, but negative edge weights create complications.

Johnson's algorithm combines several ideas developed earlier in this chapter:

Bellman-Ford
Potentials
Edge reweighting
Dijkstra

The result is an elegant all-pairs shortest-path algorithm that handles negative edge weights while remaining efficient on sparse graphs.

Problem

Given a sparse graph that may contain negative edge weights but no negative cycles, compute the shortest distance between every pair of vertices.

For example:

A -> B = 2
A -> C = 4
C -> B = -3
B -> D = 5
C -> D = 2

We want:

distance(A,B)
distance(A,C)
distance(A,D)
distance(B,A)
distance(B,C)
...

for every pair of vertices.

The graph contains a negative edge, preventing direct use of repeated Dijkstra.

Solution

Johnson's algorithm proceeds in four phases.

Phase 1: Add a Super Source

Create a new vertex:

Connect it to every vertex using zero-weight edges.

S -> A = 0
S -> B = 0
S -> C = 0
S -> D = 0

The augmented graph now contains:

Original graph
+
Super source

Phase 2: Run Bellman-Ford

Compute shortest-path distances from:

to every vertex.

These distances become potentials.

h(v)

If Bellman-Ford detects a negative cycle:

No solution exists.

The algorithm terminates.

Phase 3: Reweight Edges

For every edge:

u -> v

compute:

w'(u,v)
=
w(u,v)
+
h(u)
-
h(v)

All reweighted edges become nonnegative.

Phase 4: Run Dijkstra

Run Dijkstra once from every vertex.

The resulting distances are:

d'(u,v)

Convert them back:

d(u,v)
=
d'(u,v)
-
h(u)
+
h(v)

These are the shortest-path distances in the original graph.

High-Level Implementation

The overall structure looks like:

func johnson(graph Graph) [][]int {

	h := bellmanFordSuperSource(graph)

	reweight(graph, h)

	result := make([][]int, graph.Vertices)

	for source := 0; source < graph.Vertices; source++ {
		result[source] =
			dijkstra(graph, source)
	}

	restoreOriginalDistances(result, h)

	return result
}

Each component already exists.

Johnson's contribution is how they fit together.

Why Bellman-Ford Appears Only Once

A natural question arises.

If Bellman-Ford handles negative edges, why not run Bellman-Ford from every vertex?

The answer is cost.

Repeated Bellman-Ford requires:

V × O(VE)
=
O(V²E)

time.

Johnson runs Bellman-Ford exactly once:

O(VE)

and then uses Dijkstra for the remaining work.

The savings are substantial.

Understanding the Reweighting

Suppose:

A -> B = -3

The negative edge prevents Dijkstra from working safely.

Bellman-Ford computes:

h(A) = 4
h(B) = 1

Reweighting produces:

-3 + 4 - 1
=
0

The negative edge disappears.

Every edge becomes:

≥ 0

which satisfies Dijkstra's assumptions.

The graph becomes easier without changing shortest-path relationships.

Why Shortest Paths Remain Correct

Consider a path:

A -> C -> D -> B

Reweighting changes every edge.

At first this seems dangerous.

However:

w'(u,v)
=
w(u,v)
+
h(u)
-
h(v)

causes potentials to cancel.

The total path cost becomes:

Original cost
+
h(start)
-
h(end)

Every path between the same endpoints receives the same adjustment.

Therefore:

Cheapest path before reweighting
=
Cheapest path after reweighting

The optimal route never changes.

Example Walkthrough

Consider:

A -> B = 1
A -> C = 4
B -> C = -2
C -> D = 2

Bellman-Ford

Computes:

h(A) = 0
h(B) = 0
h(C) = -2
h(D) = 0

Reweight

A -> B
1 + 0 - 0 = 1

A -> C
4 + 0 - (-2) = 6

B -> C
-2 + 0 - (-2) = 0

C -> D
2 + (-2) - 0 = 0

All weights become nonnegative.

Dijkstra

Now operates safely from every source.

Distance Restoration

After Dijkstra computes:

d'(A,D) = 1

recover:

1 - h(A) + h(D)
=
1

which matches the original shortest-path distance.

Sparse Versus Dense Graphs

Johnson's algorithm is designed for sparse graphs.

Suppose:

V = 1000
E = 5000

Johnson requires approximately:

O(VE)
+
O(VE log V)

or:

O(VE log V)

Floyd-Warshall requires:

O(V³)

For sparse graphs:

5000 << 1000²

Johnson is dramatically faster.

For dense graphs:

E ≈ V²

the advantage largely disappears.

Comparison with Floyd-Warshall

Property	Floyd-Warshall	Johnson
Negative edges	Yes	Yes
Negative cycle detection	Yes	Yes
Sparse graph performance	Moderate	Excellent
Dense graph performance	Good	Moderate
Complexity	O(V³)	O(VE log V)
Memory	O(V²)	O(V + E) plus results

The choice depends primarily on graph density.

Discussion

Johnson's algorithm is a beautiful example of algorithm composition.

Bellman-Ford solves one problem:

Negative edges

Potentials solve another:

Edge reweighting

Dijkstra solves:

Efficient shortest paths

Combining them produces a new capability:

Efficient all-pairs shortest paths
with negative edge support.

This style of algorithm design appears frequently in advanced systems.

Instead of inventing entirely new machinery, existing algorithms are combined so that each compensates for another's weakness.

Complexity

Let:

V = vertices
E = edges

Bellman-Ford:

O(VE)

Edge reweighting:

O(E)

Repeated Dijkstra:

V × O(E log V)
=
O(VE log V)

Total:

Phase	Complexity
Bellman-Ford	O(VE)
Reweighting	O(E)
Dijkstra from every vertex	O(VE log V)
Total	O(VE log V)

For sparse graphs, this is often the best exact all-pairs algorithm available.

Common Mistakes

Do not skip the Bellman-Ford phase. Potentials must satisfy shortest-path constraints.

Do not forget to restore original distances after Dijkstra.

Do not apply Johnson's algorithm when Bellman-Ford detects a negative cycle.

Do not assume reweighted distances equal original distances. They differ by endpoint-dependent offsets.

Do not use Johnson's algorithm automatically. Dense graphs often favor Floyd-Warshall.

Practical Applications

Johnson's algorithm appears in:

Transportation networks
Route optimization systems
Telecommunications planning
Geographic information systems
Network analysis
Supply-chain optimization
Graph analytics platforms
Operations research

Large sparse networks are particularly well suited to this approach.

Takeaway

Johnson's algorithm combines Bellman-Ford, graph potentials, edge reweighting, and Dijkstra to solve the all-pairs shortest-path problem efficiently on sparse graphs. By transforming negative edge weights into nonnegative weights while preserving shortest-path relationships, it enables repeated use of Dijkstra's algorithm and achieves significantly better performance than Floyd-Warshall on large sparse networks.