Johnson's Algorithm

Johnson's Algorithm finds the shortest path between every pair of vertices in a sparse graph — even when some edges are negative — by combining Bellman-Ford and Dijkstra into one clever pipeline. The trick is a reweighting that erases negatives without changing which paths are shortest.

The slow way first

The classic all-pairs algorithm is Floyd-Warshall: it handles negatives and runs in O(V³) regardless of how many edges exist. For a sparse graph (few edges) that is wasteful — we are paying cubic time even when the graph is mostly empty.

Dijkstra from every source would be much faster on a sparse graph — O(V · E log V) — but Dijkstra breaks on negative edges. The question: can we make the weights non-negative without changing the shortest paths?

The idea: reweight away the negatives

Johnson's answer is to assign every vertex a number h(v) — a potential — and reweight each edge as w'(u,v) = w(u,v) + h(u) - h(v). Along any path the h terms telescope and cancel, so a path's reweighted length differs from its real length by a fixed h(start) - h(end). That means the shortest path is the same under either weighting.

We just need an h that makes every w' non-negative. Bellman-Ford gives it: add a virtual source q connected to all vertices with weight 0, run Bellman-Ford from q, and let h(v) be the resulting distance. The triangle inequality guarantees w + h(u) - h(v) >= 0.

Bellman-Ford runs only once; Dijkstra runs V times. Negatives are handled by the single Bellman-Ford pass, and the fast Dijkstra runs do the heavy lifting.

Walk through it

Step through the animation. First we add the virtual source q with weight-0 edges. Bellman-Ford from q produces h(A)=0, h(B)=-2, h(C)=-3. Reweighting turns A→B and B→C into 0 and A→C into 7 — all non-negative. Dijkstra from A then finds A→B→C (length 0) beats the direct edge. Finally we undo the reweighting to recover the true distance -3.

Pseudocode

add a virtual vertex q with a weight-0 edge to every vertex
h = bellman_ford(from q)        # potential for each vertex
if bellman_ford found a negative cycle:
    report it and stop
for each edge (u, v, w):
    w' = w + h(u) - h(v)        # now w' >= 0
for each source s:
    d' = dijkstra(from s, using w')
    for each vertex v:
        dist[s][v] = d'[v] - h(s) + h(v)   # undo the reweight

The Python solution

def johnson(vertices, edges):
    q = "__q__"                                  # virtual source
    aug = edges + [(q, v, 0) for v in vertices]  # weight-0 to all
    h = bellman_ford(vertices + [q], aug, q)     # potentials
    if h is None:
        raise ValueError("negative cycle")
    # reweight so every edge is non-negative
    rw = {(u, v): w + h[u] - h[v] for (u, v, w) in edges}
    dist = {}
    for s in vertices:
        d = dijkstra(vertices, rw, s)            # all >= 0 now
        for v in vertices:
            if d[v] < INF:
                dist[(s, v)] = d[v] - h[s] + h[v]  # undo reweight
    return dist

• aug adds the virtual source q with a 0-weight edge to every vertex, so q can reach all of them.
• bellman_ford from q returns the potentials h; it returns None (or similar) if a negative cycle exists.
• rw is the reweighted edge map: w + h[u] - h[v], which the potentials guarantee is non-negative.
• The inner loop runs Dijkstra from each source s on the safe non-negative weights.
• d[v] - h[s] + h[v] undoes the reweighting, recovering the real shortest distance.

Complexity

On a sparse graph (E much smaller than V²), Johnson's O(V·E·log V) beats Floyd-Warshall's O(V³). On a dense graph the two are comparable and Floyd-Warshall is simpler.

When this pattern shows up

Practice