Johnson's Algorithm

Overview

Johnson’s algorithm solves the all-pairs shortest paths (APSP) problem for sparse graphs with possibly negative edge weights. It runs Bellman-Ford once to compute a potential function $h$, uses $h$ to reweight all edges to non-negative values, then runs Dijkstra $|V|$ times. The original distances are recovered by subtracting the potential difference.

The key insight: adding a constant to every edge weight does not preserve shortest paths (longer paths accumulate more bias). Instead, the bias must depend on the endpoints: $\hat{w}(u, v) = w(u, v) + h(u) - h(v)$.

Why Naive Reweighting Fails

Adding a fixed constant $b$ to every edge weight makes all edges non-negative, but changes which paths are shortest. If two paths from $A$ to $B$ have 2 edges and 5 edges respectively, the 5-edge path accumulates $5b$ vs $2b$, so the ranking can change. Johnson’s vertex-potential reweighting avoids this.

The Reweighting Function

Given a function $h: V \to \mathbb{R}$, define the reweighted edge weight:

$\hat{w}(u, v) = w(u, v) + h(u) - h(v)$

Property 1 (shortest-path preservation): For any path $p = v_1 \to v_2 \to \cdots \to v_k$:

$\hat{w}(p) = \sum_{i=1}^{k-1} (w(v_i, v_{i+1}) + h(v_i) - h(v_{i+1})) = w(p) + h(v_1) - h(v_k)$

The terms telescope: $h(v_i)$ and $-h(v_{i+1})$ cancel for interior vertices. The difference $h(v_1) - h(v_k)$ depends only on the endpoints, not the path. Therefore $\hat{w}$ preserves the relative ordering of paths between any fixed pair of vertices: a shortest path under $w$ is also a shortest path under $\hat{w}$.

Property 2 (non-negative weights): If $h(v) = \delta(s, v)$ (the true shortest distance from some source $s$), then by the triangle inequality $\delta(s, v) \le \delta(s, u) + w(u, v)$, so:

$\hat{w}(u, v) = w(u, v) + h(u) - h(v) \ge 0$

Algorithm

1. Augment $G$ to $G'$: add a new vertex $s$ connected to every $v \in V$ with weight 0. $G'$ has no new negative cycles.
2. Run Bellman-Ford on $G'$ from $s$. If it detects a negative cycle, report failure. Otherwise, set $h(v) = \delta(s, v)$ for all $v$.
3. Reweight every original edge: $\hat{w}(u, v) = w(u, v) + h(u) - h(v)$. Now all edges have non-negative weight.
4. For each vertex $u \in V$, run Dijkstra on the reweighted graph to get $\hat{\delta}(u, v)$ for all $v$.
5. Recover true distances: $\delta(u, v) = \hat{\delta}(u, v) - h(u) + h(v)$.

Pseudocode:

JOHNSON(G, w):
  G' = (V ∪ {s}, E ∪ {(s,v) : v ∈ V}) with w(s,v)=0
  if BELLMAN-FORD(G', w, s) == FALSE:
    error("negative cycle")
  for each edge (u,v) in G.E:
    ŵ(u,v) = w(u,v) + u.d - v.d      // u.d = δ(s,u)
  D = new |V|×|V| matrix
  for each u in G.V:
    DIJKSTRA(G, ŵ, u)
    for each v in G.V:
      D[u][v] = v.d - u.h + v.h        // undo reweighting
  return D

Worked Example

Consider a graph with $V = \{1,2,3\}$ and edges: $1 \to 2$ (weight $-2$), $1 \to 3$ (weight $4$), $2 \to 3$ (weight $1$). This has a negative edge $1 \to 2$ but no negative cycles.

Step 1: Augment with $s$, edges $s \to 1, s \to 2, s \to 3$ (weight 0).

Step 2: Bellman-Ford from $s$ gives $h(1)=0$, $h(2)=0$, $h(3)=0$ (there are no paths to improve, since $s$ edges are 0-weight). Actually, with the original edges present: $h(1)=0$, $h(2)=-2$, $h(3)=-1$ (path $s \to 1 \to 2 \to 3$ costs $0-2+1=-1$, or $s \to 1 \to 3$ costs $4$).

Step 3: Reweight:

• $\hat{w}(1,2) = -2 + 0 - (-2) = 0$
• $\hat{w}(1,3) = 4 + 0 - (-1) = 5$
• $\hat{w}(2,3) = 1 + (-2) - (-1) = 0$

All reweighted edges are non-negative.

Step 4: Run Dijkstra from 1: $\hat{\delta}(1,2)=0$, $\hat{\delta}(1,3)=0$ (via $1 \to 2 \to 3$).

Step 5: Recover: $\delta(1,2) = 0 - 0 + (-2) = -2$, $\delta(1,3) = 0 - 0 + (-1) = -1$.

Results match the original graph (path $1 \to 2 \to 3$ costs $-2+1=-1$).

Running Time

• Step 1: $\Theta(|V|)$.
• Step 2: $\Theta(|V|\cdot|E|)$ (Bellman-Ford).
• Step 3: $\Theta(|E|)$.
• Step 4: $|V|$ calls to Dijkstra. With binary heap: $O(|V| \cdot (|V|+|E|)\log|V|) = O(|V| \cdot |E| \log |V|)$. With Fibonacci heap: $O(|V|^2 \log |V| + |V| \cdot |E|)$.
• Step 5: $\Theta(|V|^2)$.

Total: $O(|V|^2 \log |V| + |V| \cdot |E|)$ with Fibonacci heap, or $O(|V| \cdot |E| \log |V|)$ with binary heap.

Comparison with Floyd-Warshall

Algorithm	Time	Best for
Johnson	$O(V^2 \log V + VE)$	Sparse graphs
Floyd-Warshall	$\Theta(V^3)$	Dense graphs

Johnson wins when $|E| = o(|V|^2)$. When $|E| = \Theta(|V|^2)$, Floyd-Warshall’s simpler implementation and smaller constant factor make it preferable.

Summary

Step	Operation	Time
Augment	Add dummy $s$	$O(V)$
Bellman-Ford	Compute $h(v)$	$O(VE)$
Reweight	$\hat{w} = w + h(u) - h(v)$	$O(E)$
Dijkstra × $V$	All-pairs	$O(V \cdot E \log V)$
Un-reweight	$D[u][v] + h(u) - h(v)$	$O(V^2)$

Past paper questions: y2024p1q9 (reweighting, relaxed costs, opportunities).