1. One-Liner
Johnson computes all-pairs shortest paths by reweighting edges with Bellman-Ford potentials so weights become non-negative, then running Dijkstra from each vertex — efficient on sparse graphs with possible negative edges (no negative cycles).
2. The Problem It Solves
APSP like Floyd-Warshall but faster sparse graphs; handles negative edge weights (not negative cycles) where naive Dijkstra fails.
3. The Core Idea
Add a super-source connected to all nodes with 0 edges; h[v] = shortest distance from super-source (Bellman-Ford). New weight w'(u,v)=w(u,v)+h[u]−h[v] is non-negative if no negative cycle; then Dijkstra with w'.
4. How It Works (Step-by-Step)
| Step | Action |
|---|---|
| 1 | Run Bellman-Ford from super-source to get h[] |
| 2 | If relax still works → negative cycle |
| 3 | Reweight each edge |
| 4 | For each u: Dijkstra on w' |
| 5 | Distances: d'(u,v) − h[u] + h[v] |
5. Dry Run Example
Negative edge reweighted to non-negative potentials; Dijkstra then matches true shortest paths after unreweighting.
6. Key Properties
| Property | Value |
|---|---|
| Sparse | O(V² log V + VE) typical |
| Dense | Floyd may win |
7. Where It Is Used
| Domain | Use |
|---|---|
| OR / routing | APSP with negatives sparse |
| Libraries | Theoretical baseline |
8. Interview Tips
Explain why reweighting preserves shortest paths; triangle inequality on transformed weights.
9. Comparison with Other Algorithms
| Johnson | Floyd-Warshall | V×BF | |
|---|---|---|---|
| Sparse | Strong | O(V³) weak | O(V²E) slow |
10. Complexity
| -- | -- |
|---|---|
| Time | O(V E log V + V E) ≈ O(V E log V) with BF + Dijkstra |
| Space | O(V + E) |
Implementation Example (PYTHON)
import heapq
def johnson(n, edges):
INF = 10**18
src = n
bell = [(src, i, 0) for i in range(n)] + list(edges)
N = n + 1
dist = [INF] * N
dist[src] = 0
for _ in range(N - 1):
for u, v, w in bell:
if dist[u] < INF and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
for u, v, w in bell:
if dist[u] + w < dist[v]:
return None
h = dist[:n]
adj = [[] for _ in range(n)]
for u, v, w in edges:
adj[u].append((v, w + h[u] - h[v]))
def dijkstra(s):
d = [INF] * n
d[s] = 0
pq = [(0, s)]
while pq:
du, u = heapq.heappop(pq)
if du != d[u]: continue
for v, w in adj[u]:
nd = du + w
if nd < d[v]:
d[v] = nd
heapq.heappush(pq, (nd, v))
return d
out = []
for s in range(n):
ds = dijkstra(s)
out.append([ds[i] - h[s] + h[i] if ds[i] < INF else INF for i in range(n)])
return out