Algorithm Deep Dive: Johnson's Algorithm

A Bit of History

Donald B. Johnson published “Efficient Algorithms for Shortest Paths in Sparse Networks” in 1977. The algorithm fills an important gap between Floyd–Warshall, whose $O(V^3)$ running time ignores sparsity, and Dijkstra's algorithm, which exploits sparse adjacency lists but requires nonnegative weights.

Johnson's contribution is a composition of ideas: Bellman–Ford supplies a feasible potential function, reduced costs make Dijkstra legal, and a final algebraic correction restores the original distances.

The Sparse All-Pairs Shortest-Path Gap

Given a directed weighted graph $G=(V,E)$, all-pairs shortest paths asks for $\delta(s,t)$ for every ordered pair of vertices. Negative edges are allowed, but a reachable negative cycle makes some distances unbounded below: walking around that cycle repeatedly keeps reducing the path cost.

Dijkstra

Fast but restricted

Adjacency lists and a heap are efficient on sparse graphs, but a negative edge breaks the greedy settled-distance argument.

Bellman–Ford

General but repeated

It handles negative edges and detects negative cycles, but running it from every source costs $O(V^2E)$.

Johnson

Transform once

One Bellman–Ford pass makes every later source search compatible with Dijkstra.

The goal is not to preserve each edge's weight. It is to preserve the ordering of all paths that share the same start and end.

The Four-Stage Pipeline

Make every vertex reachable. Add a temporary source $q$ with a zero-weight edge $q\to v$ to every original vertex.
Compute potentials. Run Bellman–Ford from $q$. Its distance $h(v)=\delta(q,v)$ becomes the potential of $v$. A further relaxation means a negative cycle exists, so Johnson must stop.
Build reduced weights. Replace every edge weight by $w'(u,v)=w(u,v)+h(u)-h(v)$. These values are nonnegative.
Search and restore. Run Dijkstra from every original source with $w'$, then convert finite answers back using $\delta(s,t)=\delta'(s,t)-h(s)+h(t)$.

Implementations often avoid materializing $q$: initializing every potential to zero has the same effect as relaxing all zero-weight edges from the super-source once.

Potentials Turn Negative Edges Nonnegative

For the five-vertex example used in the implementations, Bellman–Ford computes $h=[0,-1,-5,0,-4]$. The potential is not an answer to an original source query; it is a globally consistent price adjustment. Four representative edges show how the adjustment works:

The super-source ensures Bellman–Ford reaches every component. Negative original weights are allowed; the reduced weights are all nonnegative and therefore safe for Dijkstra.

Why Must Every Reweighted Edge Be Nonnegative?

Because $h(v)$ is a shortest distance from $q$, taking a shortest route to $u$ and then edge $(u,v)$ cannot beat the optimum to $v$:

h(v)\le h(u)+w(u,v).

Rearranging gives $w(u,v)+h(u)-h(v)\ge0$, which is exactly $w'(u,v)\ge0$. This inequality is the bridge between Bellman–Ford and Dijkstra: Bellman–Ford certifies a potential that makes every reduced cost feasible.

Why Reweighting Preserves Shortest Paths

For a path $P=v_0\to v_1\to\cdots\to v_k$, sum the reweighted edges:

w'(P)=\sum_{i=1}^{k}\left[w(v_{i-1},v_i)+h(v_{i-1})-h(v_i)\right]=w(P)+h(v_0)-h(v_k).

Every intermediate potential appears once positively and once negatively, so it cancels. All paths with the same endpoints receive the same correction $h(v_0)-h(v_k)$. Their absolute costs change, but their ordering does not.

Each edge label shows “original / reweighted.” Since $h(0)-h(1)=1$, both candidate paths gain exactly 1. The four-edge path remains cheaper than the direct edge.

Why a Negative Cycle Stops the Algorithm

If Bellman–Ford can still relax an edge after the normal passes, some negative cycle is reachable from $q$. Because $q$ reaches every original vertex, that detects a negative cycle anywhere in the graph. For pairs that can enter and later leave such a cycle, there is no finite shortest distance: another lap always makes the walk cheaper.

Not Merely a Dijkstra Limitation

No all-pairs algorithm can return ordinary finite shortest distances for every pair in this situation. Johnson therefore rejects the graph before reweighting. If the actual cycle is needed, store predecessors during Bellman–Ford and reconstruct it.

Complexity Analysis

Stage	Binary-heap implementation	Purpose
Bellman–Ford	$O(VE)$	Compute potentials and detect any negative cycle.
Reweighting	$O(E)$	Build a nonnegative adjacency list.
$V$ Dijkstra runs	$O\!\left(V(E+V)\log V\right)$	Compute one distance row per source.
Distance matrix	$O(V^2)$ space	Store all ordered-pair answers; streaming rows can reduce output memory.

On the usual sparse connected case $E=\Omega(V)$, the binary-heap total is commonly summarized as $O(VE\log V)$. With Fibonacci heaps, the Dijkstra portion becomes $O(VE+V^2\log V)$, matching the bound often quoted for Johnson's original analysis. Floyd–Warshall remains $O(V^3)$ regardless of $E$ and may be preferable for dense graphs or compact matrix-based implementations.

Implementation

All three versions use wide integer distances, validate endpoints, stop Bellman–Ford early when stable, preserve infinity for unreachable pairs, and return both the distance matrix and potentials. A null result indicates a negative cycle.

import heapq

def johnson(n, edges):
    """Return (distance_matrix, potentials), or None for a negative cycle."""
    if n < 0:
        raise ValueError("n must be nonnegative")
    for u, v, _ in edges:
        if not (0 <= u < n and 0 <= v < n):
            raise ValueError("edge endpoint outside 0..n-1")

    # Bellman–Ford with an implicit super-source q.
    h = [0] * n
    for _ in range(max(0, n - 1)):
        changed = False
        for u, v, w in edges:
            if h[u] + w < h[v]:
                h[v] = h[u] + w
                changed = True
        if not changed:
            break
    if any(h[u] + w < h[v] for u, v, w in edges):
        return None

    adj = [[] for _ in range(n)]
    for u, v, w in edges:
        reduced = w + h[u] - h[v]
        if reduced < 0:
            raise AssertionError("negative reduced weight")
        adj[u].append((v, reduced))

    inf = float("inf")
    matrix = [[inf] * n for _ in range(n)]
    for source in range(n):
        reduced_dist = [inf] * n
        reduced_dist[source] = 0
        queue = [(0, source)]
        while queue:
            distance_u, u = heapq.heappop(queue)
            if distance_u != reduced_dist[u]:
                continue
            for v, reduced in adj[u]:
                candidate = distance_u + reduced
                if candidate < reduced_dist[v]:
                    reduced_dist[v] = candidate
                    heapq.heappush(queue, (candidate, v))

        for target, value in enumerate(reduced_dist):
            if value != inf:
                matrix[source][target] = value - h[source] + h[target]

    return matrix, h


edges = [
    (0,1,3), (0,2,8), (0,4,-4), (1,3,1), (1,4,7),
    (2,1,4), (3,0,2), (3,2,-5), (4,3,6)
]
distances, potentials = johnson(5, edges)
print("h =", potentials)
for row in distances:
    print(row)

#include <functional>
#include <iostream>
#include <limits>
#include <queue>
#include <stdexcept>
#include <utility>
#include <vector>
using namespace std;

using Weight = long long;
const Weight INF = numeric_limits<Weight>::max() / 4;
struct Edge { int u, v; Weight w; };

bool johnson(int n, const vector<Edge>& edges,
             vector<vector<Weight>>& matrix, vector<Weight>& h) {
    if (n < 0) throw invalid_argument("n must be nonnegative");
    for (const Edge& e : edges)
        if (e.u < 0 || e.u >= n || e.v < 0 || e.v >= n)
            throw invalid_argument("edge endpoint outside 0..n-1");

    // Bellman–Ford with an implicit zero-edge super-source.
    h.assign(n, 0);
    for (int iteration = 0; iteration < n - 1; ++iteration) {
        bool changed = false;
        for (const Edge& e : edges) {
            if (h[e.u] + e.w < h[e.v]) {
                h[e.v] = h[e.u] + e.w;
                changed = true;
            }
        }
        if (!changed) break;
    }
    for (const Edge& e : edges)
        if (h[e.u] + e.w < h[e.v]) return false;

    vector<vector<pair<int, Weight>>> adj(n);
    for (const Edge& e : edges) {
        Weight reduced = e.w + h[e.u] - h[e.v];
        if (reduced < 0) throw logic_error("negative reduced weight");
        adj[e.u].push_back({e.v, reduced});
    }

    matrix.assign(n, vector<Weight>(n, INF));
    for (int source = 0; source < n; ++source) {
        vector<Weight> reducedDist(n, INF);
        priority_queue<pair<Weight, int>,
                       vector<pair<Weight, int>>,
                       greater<pair<Weight, int>>> queue;
        reducedDist[source] = 0;
        queue.push({0, source});

        while (!queue.empty()) {
            auto [distanceU, u] = queue.top(); queue.pop();
            if (distanceU != reducedDist[u]) continue;
            for (auto [v, reduced] : adj[u]) {
                Weight candidate = distanceU + reduced;
                if (candidate < reducedDist[v]) {
                    reducedDist[v] = candidate;
                    queue.push({candidate, v});
                }
            }
        }

        for (int target = 0; target < n; ++target)
            if (reducedDist[target] != INF)
                matrix[source][target] = reducedDist[target] - h[source] + h[target];
    }
    return true;
}

int main() {
    vector<Edge> edges = {
        {0,1,3},{0,2,8},{0,4,-4},{1,3,1},{1,4,7},
        {2,1,4},{3,0,2},{3,2,-5},{4,3,6}
    };
    vector<vector<Weight>> distances;
    vector<Weight> potentials;
    if (!johnson(5, edges, distances, potentials)) return 1;
    for (const auto& row : distances) {
        for (Weight value : row) cout << value << ' ';
        cout << '\n';
    }
}

import java.util.*;

class Johnsons {
    static final long INF = Long.MAX_VALUE / 4;
    record Edge(int u, int v, long weight) {}
    record Arc(int to, long weight) {}
    record Result(long[][] distances, long[] potentials) {}

    static Result solve(int n, List<Edge> edges) {
        if (n < 0) throw new IllegalArgumentException("n must be nonnegative");
        for (Edge e : edges)
            if (e.u() < 0 || e.u() >= n || e.v() < 0 || e.v() >= n)
                throw new IllegalArgumentException("edge endpoint outside 0..n-1");

        // Bellman–Ford with an implicit zero-edge super-source.
        long[] h = new long[n];
        for (int iteration = 0; iteration < n - 1; iteration++) {
            boolean changed = false;
            for (Edge e : edges) {
                if (h[e.u()] + e.weight() < h[e.v()]) {
                    h[e.v()] = h[e.u()] + e.weight();
                    changed = true;
                }
            }
            if (!changed) break;
        }
        for (Edge e : edges)
            if (h[e.u()] + e.weight() < h[e.v()]) return null;

        List<List<Arc>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (Edge e : edges) {
            long reduced = e.weight() + h[e.u()] - h[e.v()];
            if (reduced < 0) throw new IllegalStateException("negative reduced weight");
            adj.get(e.u()).add(new Arc(e.v(), reduced));
        }

        long[][] matrix = new long[n][n];
        for (long[] row : matrix) Arrays.fill(row, INF);

        for (int source = 0; source < n; source++) {
            long[] reducedDist = new long[n];
            Arrays.fill(reducedDist, INF);
            reducedDist[source] = 0;
            PriorityQueue<long[]> queue =
                new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
            queue.add(new long[]{0, source});

            while (!queue.isEmpty()) {
                long[] current = queue.poll();
                long distanceU = current[0];
                int u = (int) current[1];
                if (distanceU != reducedDist[u]) continue;
                for (Arc arc : adj.get(u)) {
                    long candidate = distanceU + arc.weight();
                    if (candidate < reducedDist[arc.to()]) {
                        reducedDist[arc.to()] = candidate;
                        queue.add(new long[]{candidate, arc.to()});
                    }
                }
            }

            for (int target = 0; target < n; target++)
                if (reducedDist[target] != INF)
                    matrix[source][target] =
                        reducedDist[target] - h[source] + h[target];
        }
        return new Result(matrix, h);
    }

    public static void main(String[] args) {
        List<Edge> edges = List.of(
            new Edge(0,1,3), new Edge(0,2,8), new Edge(0,4,-4),
            new Edge(1,3,1), new Edge(1,4,7), new Edge(2,1,4),
            new Edge(3,0,2), new Edge(3,2,-5), new Edge(4,3,6)
        );
        Result result = solve(5, edges);
        for (long[] row : result.distances())
            System.out.println(Arrays.toString(row));
    }
}

Choosing an All-Pairs Algorithm

Method	Negative edges	Negative-cycle check	Typical time	Best fit
Repeated Dijkstra	No	No	$O(V(E+V)\log V)$	Sparse graph with nonnegative weights
Johnson	Yes	Yes	$O(VE\log V)$ with binary heaps on typical sparse graphs	Sparse directed graph with negative edges but no negative cycle
Floyd–Warshall	Yes	Yes, via negative diagonal entries	$O(V^3)$	Dense graphs, simple matrix code, or modest $V$
Repeated Bellman–Ford	Yes	Yes	$O(V^2E)$	Simple baseline; rarely the fastest APSP choice

If only a handful of sources matter, running a suitable single-source algorithm for those sources is often better than materializing a full $V\times V$ matrix. Johnson is specifically an all-pairs strategy.

Where Johnson's Structure Helps

Sparse Route Tables

Compute directed route costs between every pair when adjustments or credits can make some edges negative.

Dependency Analysis

Answer many influence or transition-cost queries in a sparse directed dependency network.

Distance Precomputation

Build an exact distance oracle for a moderate sparse graph when repeated queries justify $O(V^2)$ output.

Arbitrage Screening

After negative-log conversion, Bellman–Ford's failure can flag a negative cycle; cycle reconstruction needs predecessors.

Reduced-Cost Intuition

The potential transformation mirrors reduced costs used throughout optimization and min-cost-flow algorithms.

Row Streaming

If consumers process one source at a time, Dijkstra rows can be emitted without retaining the full matrix.

Pitfalls and Edge Cases

Mistake	Consequence	Robust treatment
Running Dijkstra on original negative weights	Settled vertices may later receive shorter paths.	Run it only on the nonnegative reduced graph.
Forgetting the super-source	A negative cycle in another component may be missed.	Connect $q$ to every vertex, or initialize every $h(v)$ to zero.
Using the wrong restore sign	Every finite answer is shifted incorrectly.	Use $d=d'-h(s)+h(t)$.
Converting infinity algebraically	An unreachable pair becomes a huge or nonsensical number.	Restore only finite Dijkstra distances.
Using 32-bit path totals	Long paths overflow even when each edge fits.	Use wide integers and leave headroom below the infinity sentinel.
Confusing directed and undirected negative edges	One negative undirected edge creates a two-edge negative cycle.	Johnson is mainly meaningful for directed graphs when negative edges exist.
Always storing the matrix	$O(V^2)$ output dominates memory.	Stream or consume one source row when the API permits.

Directedness Matters

In an undirected representation, an edge of weight $-2$ means both $u\to v$ and $v\to u$ have weight $-2$, immediately producing a cycle of total $-4$. Negative-edge MST problems are different; Johnson solves directed shortest paths.

Exercises

Work with Potentials, Not Memorized Steps

Reweight. Use $h=[0,-1,-5,0,-4]$ to calculate $w'$ for all nine sample edges and verify that none is negative.
Telescope. Expand the potential terms on $0\to4\to3\to2\to1$ and cross out each intermediate cancellation.
Restore. Dijkstra gives $d'(0,2)=2$. Recover the original $d(0,2)$ and check it against the path $0\to4\to3\to2$.
Detect. Add edge $1\to0$ of weight $-4$. Identify a negative cycle and explain which Bellman–Ford inequality keeps improving.
Disconnect. Add an isolated vertex 5. Predict its potential and all matrix entries involving it.
Extend. Store a predecessor array for each Dijkstra run so a caller can reconstruct an actual shortest path.

Sanity checks: every diagonal distance is zero, every reduced edge is nonnegative, and reachable answers satisfy $d(s,v)\le d(s,u)+w(u,v)$.

Cookie Consent

Johnson's Algorithm

Contents

A Bit of History

The Sparse All-Pairs Shortest-Path Gap

Fast but restricted

General but repeated

Transform once

The Four-Stage Pipeline

Potentials Turn Negative Edges Nonnegative

Why Must Every Reweighted Edge Be Nonnegative?

Why Reweighting Preserves Shortest Paths

Why a Negative Cycle Stops the Algorithm

Not Merely a Dijkstra Limitation

Complexity Analysis

Implementation

Choosing an All-Pairs Algorithm

Where Johnson's Structure Helps

Sparse Route Tables

Dependency Analysis

Distance Precomputation

Arbitrage Screening

Reduced-Cost Intuition

Row Streaming

Pitfalls and Edge Cases

Directedness Matters

Exercises

Work with Potentials, Not Memorized Steps

Cookie Consent

Johnson's Algorithm

Contents

A Bit of History

The Sparse All-Pairs Shortest-Path Gap

Fast but restricted

General but repeated

Transform once

The Four-Stage Pipeline

Potentials Turn Negative Edges Nonnegative

Why Must Every Reweighted Edge Be Nonnegative?

Why Reweighting Preserves Shortest Paths

Why a Negative Cycle Stops the Algorithm

Not Merely a Dijkstra Limitation

Complexity Analysis

Implementation

Choosing an All-Pairs Algorithm

Where Johnson's Structure Helps

Sparse Route Tables

Dependency Analysis

Distance Precomputation

Arbitrage Screening

Reduced-Cost Intuition

Row Streaming

Pitfalls and Edge Cases

Directedness Matters

Exercises

Work with Potentials, Not Memorized Steps

Related Deep Dives

Graph Theory Series

Bellman-Ford Algorithm

Floyd-Warshall Algorithm