Johnson's Algorithm — All-Pairs Shortest Paths on Sparse Graphs

The Story That Explains Johnson's Algorithm

Johnson's Algorithm solves the All-Pairs Shortest Paths (APSP) problem on sparse weighted directed graphs that may contain negative edge weights (but no negative-weight cycles). It combines two classic algorithms into one elegant pipeline and achieves O(V² log V + VE) — dramatically faster than Floyd-Warshall's Θ(V³) when the graph is sparse.

The Four Phases — High-Level Pipeline

Johnson's algorithm runs in four clearly distinct phases. Click each phase to highlight it.

The Reweighting Formula — Why It Works

The heart of Johnson's Algorithm is this elegant transformation. Understanding why it preserves shortest paths is the key to mastering the algorithm.

Animated Example — Phase 2: Bellman-Ford Trace

We run Bellman-Ford on this concrete 5-vertex graph (4 original + virtual source s). Click Next Relaxation to step through each edge relaxation and watch the h-values converge.

Animated Example — Phase 3: Edge Reweighting

Using the potentials h(v) computed in Phase 2, we now transform every edge weight. Click through each edge to see the formula applied live.

Animated Example — Phase 4: Dijkstra from Source 1

With all edges non-negative, we run Dijkstra once for each source. Here we trace Dijkstra from vertex 1 on the reweighted graph. Step through to see distances settle, then apply the recovery formula to get true distances.

Python Implementation — Full Code with Step Tracer

Below is a complete, production-quality Python implementation of Johnson's Algorithm using a min-heap for Dijkstra. Click Step Through → to advance one major code block at a time with live explanation and variable state.

import heapq
import math

def bellman_ford(graph, source, n):
    # Returns h[v] = shortest-path from source
    h = [math.inf] * (n + 1)
    h[source] = 0
    for _ in range(n - 1):       # n-1 passes
        for u, v, w in graph:   # relax every edge
            if h[u] + w < h[v]:
                h[v] = h[u] + w
    # Negative cycle check
    for u, v, w in graph:
        if h[u] + w < h[v]:
            raise ValueError("Negative-weight cycle")
    return h

def dijkstra(adj, source, n, h):
    # Min-heap Dijkstra on reweighted graph
    dist = [math.inf] * (n + 1)
    dist[source] = 0
    pq = [(0, source)]        # (distance, vertex)
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]: continue  # stale entry
        for v, w in adj[u]:      # neighbours of u
            w_hat = w + h[u] - h[v]  # reweighted cost
            if dist[u] + w_hat < dist[v]:
                dist[v] = dist[u] + w_hat
                heapq.heappush(pq, (dist[v], v))
    return dist

def johnsons(n, edges):
    # n: vertex count (1-indexed)
    # edges: list of (u, v, w)

    # Phase 1: Add virtual source s = n+1
    aug = edges + [(n+1, v, 0) for v in range(1, n+1)]

    # Phase 2: Bellman-Ford for potentials
    h = bellman_ford(aug, n+1, n+1)

    # Build adjacency list for Dijkstra
    adj = [[] for _ in range(n+2)]
    for u, v, w in edges:
        adj[u].append((v, w))   # original weights

    # Phase 4: Dijkstra from every source
    D = {}  # D[u][v] = true shortest path
    for u in range(1, n+1):
        dist = dijkstra(adj, u, n, h)
        D[u] = {}
        for v in range(1, n+1):
            if dist[v] == math.inf:
                D[u][v] = math.inf
            else:
                # Recover true distance
                D[u][v] = dist[v] - h[u] + h[v]
    return D

Complete Worked Example — End to End

Let's trace Johnson's Algorithm on a 5-vertex graph with two negative edges and print the full all-pairs distance matrix.

# ── Johnson's Algorithm — complete demo ──────────────────────────

edges = [
    (1, 2,  3),   # 1→2  weight  3
    (1, 3,  8),   # 1→3  weight  8
    (2, 4,  1),   # 2→4  weight  1
    (3, 2, -4),   # 3→2  weight -4  ← negative
    (4, 3,  2),   # 4→3  weight  2
    (4, 5,  6),   # 4→5  weight  6
    (5, 1, -3),   # 5→1  weight -3  ← negative
    (5, 4,  7),   # 5→4  weight  7
]

D = johnsons(5, edges)

# Print all-pairs matrix
print("All-Pairs Shortest Path Matrix:")
print(f"{'':4s}", end="")
for j in range(1, 6):
    print(f"{j:6d}", end="")
print()
for i in range(1, 6):
    print(f"{i:4d}", end="")
    for j in range(1, 6):
        val = D[i][j]
        sym = "  ∞" if val == math.inf else f"{val:6.0f}"
        print(sym, end="")
    print()

Complexity Analysis — Why Johnson's Wins on Sparse Graphs

Visual Pipeline — Full Algorithm Diagram

Real-World Use Cases & Benefits

CLRS Chapter Context — Where Johnson's Fits

Edge Cases, Traps & Common Mistakes

Full APSP Algorithm Comparison

Golden Rules — Johnson's Algorithm in Practice