Abstract flowing gradient in deep indigo and blue tones, smooth and luminous, evoking a modern digital learning atmosphere

Computer Science and programming articles. We do not sell courses.

Finding shortest paths between every pair of vertices with the Johnson algorithm

When you need the shortest route between every pair of points on a map, you are facing the all-pairs shortest path problem. It appears in logistics planning, network routing, traffic simulation, and even the dispatch algorithms that move freight across the Nullarbor Plain between Perth and Sydney. The Johnson algorithm, published in 1977 by Donald B. Johnson, gives one of the most efficient ways to compute these distances for sparse graphs that may contain edges with negative weights, provided no negative cycle exists.

The method combines two classical algorithms into a single pipeline. A Bellman-Ford pass produces a reweighting of the graph that removes negative edge weights, after which Dijkstra's algorithm can be run from every vertex to obtain all pairwise distances in their final form. The result is a solution that runs faster than Floyd-Warshall on most practical inputs and handles a wider class of graphs than Dijkstra alone.

Why all-pairs shortest paths matter

The all-pairs shortest path question comes up whenever a system needs to know how to travel efficiently between any two points in a network. A delivery company in Melbourne dispatching vans across the city's tram-shadowed laneways might want to compute optimal pairings between pickup and drop-off addresses. A rideshare platform operating in Brisbane, Canberra, and Adelaide needs the same kind of lookup to suggest fair fares and ETAs. Even static problems like finding the centre of a road network or estimating driving distances between postcodes rely on having pairwise distances ready.

Compared to single-source shortest path problems, the all-pairs version returns a full distance matrix. This matrix can answer follow-up questions: which pair of cities is closest, which road segment acts as a bottleneck, and where the network becomes disconnected. Many graph libraries expose this functionality through a single function call, but understanding what happens under the hood helps when the underlying graph behaves unexpectedly. Readers exploring broader algorithmic foundations can find related material on the machine learning resources hub.

Common situations where the all-pairs solution earns its keep include:

Johnson's approach is particularly attractive when the input graph is sparse. A sparse graph has roughly as many edges as it has vertices, which is typical for road networks, telecommunications backbones, and supply graphs in operations research. In those settings, Johnson's pipeline runs in O(V² log V + V·E) time, beating the O(V³) cost of the older Floyd-Warshall algorithm whenever E is much smaller than V².

The core idea: reweighting with Bellman-Ford

Dijkstra's algorithm finds single-source shortest paths in O(E + V log V) time when all edge weights are non-negative. The moment a graph contains a negative edge weight, Dijkstra's greedy expansion can skip over a vertex whose true distance is still improving, which breaks its correctness. Bellman-Ford handles negative weights but only runs in O(V·E) time, which is too slow to repeat from every source.

Johnson's contribution is a clever workaround: reweight the graph so that every edge becomes non-negative, then run Dijkstra from every vertex. The reweighting uses a potential function h(v) assigned to each vertex. A new weight w'(u, v) = w(u, v) + h(u) - h(v) replaces the original w(u, v). Because every path from s to t picks up h(s) at the start and loses h(t) at the end, the ordering of path lengths is preserved. If w'(u, v) is non-negative for every edge, Dijkstra can run safely from each vertex.

To obtain the potential function h, Johnson adds a new source vertex connected to all existing vertices by zero-weight edges, then runs Bellman-Ford from this new source. The resulting shortest distances from the artificial source become the h values. If Bellman-Ford detects a negative cycle during this pass, Johnson halts and reports the cycle, because no meaningful shortest paths can exist in a graph with one. Concepts like this reweighting transformation connect to broader mathematical ideas covered in tutorials such as the support vector machine mathematics guide, where careful reparameterisation and convex optimisation play a similar structural role.

Running Dijkstra from every vertex

Once the reweighted graph contains only non-negative edges, the next phase is straightforward. Run Dijkstra's algorithm from each vertex v in the original graph, treating the reweighted edge costs as the values to minimise. Each run returns an array dist'[v][u] for every target vertex u. To recover the original distance, apply the inverse transformation: dist[v][u] = dist'[v][u] - h(v) + h(u).

In practice, this loop is often implemented with a binary heap or a Fibonacci heap. With a Fibonacci heap, each Dijkstra call costs O(E + V log V), giving an overall running time of O(V·E + V² log V). For a graph representing the streets of Greater Sydney, where V might be the number of intersections and E the number of road segments, this gives excellent performance compared with brute-force approaches that recompute paths on demand.

The output of this phase is a complete distance matrix indexed by source and destination vertex. From there, path reconstruction follows the usual pattern: each Dijkstra invocation stores a predecessor for every reachable vertex, and the full shortest path from s to t is recovered by walking back through predecessors from t to s. Because the reweighting transformation is invertible, the reconstructed paths remain valid in the original graph even though the algorithm worked entirely in reweighted space.

Detecting negative cycles and handling edge cases

A negative cycle is a directed loop whose edge weights add to a negative number. Walking around such a cycle repeatedly makes the total path length arbitrarily small, which means no shortest path exists between certain vertex pairs. Johnson's algorithm detects these cycles during the Bellman-Ford phase. If any edge relaxes after V - 1 iterations, Bellman-Ford returns false, and Johnson reports a negative cycle rather than a distance matrix.

This detection matters in real systems. In Australia, route-planning software used by freight operators must avoid datasets with negative cycle artefacts that arise from faulty cost models or stale toll-road data. The ACCC's focus on transparent pricing in industries such as ride-booking and freight has pushed operators to maintain cleaner graph models, where negative cycles are rare but worth catching early. When a negative cycle does appear, downstream code usually flags the affected region, recalculates affected paths using bounded penalties, or falls back to a simpler heuristic.

Another edge case arises when the graph is disconnected. Dijkstra run from a vertex only reaches the component containing it, so the returned distance is effectively infinity for vertices in other components. Johnson treats these entries as undefined or, depending on the implementation, marks them with a sentinel value such as None or a very large constant. Path reconstruction in disconnected components is left as a separate concern.

A final practical note: Johnson's algorithm assumes the input is a directed graph. For undirected graphs, each undirected edge must be replaced with two directed edges of equal weight. Negatively weighted undirected edges create negative cycles of length two, which Bellman-Ford will catch during reweighting, so Johnson remains a sound choice.

Implementation details and complexity

A typical implementation follows three stages. First, add a new source vertex q connected to every other vertex with a zero-weight edge. Second, run Bellman-Ford from q to compute the potential function h and check for negative cycles. Third, reweight each edge, run Dijkstra from every original vertex, and transform the resulting distances back.

Key stages of Johnson's pipeline include:

The asymptotic complexity depends on the priority queue used in Dijkstra. With a binary heap, the total is O(V·E + V² log V). With a Fibonacci heap, this becomes O(V·E + V² log V) as well, though constants improve. For dense graphs where E approaches V², Floyd-Warshall wins at O(V³) without the constants of repeated Dijkstra calls. For sparse graphs where E is closer to V, Johnson's approach is the clear choice.

When implementing, watch out for integer overflow when the graph weights and potentials are large. Many libraries work with 64-bit integers or floating-point numbers to avoid this. Watch also for the cost of allocating the predecessor arrays V times; a flat matrix or compressed storage layout makes the constant factors smaller. In Python, using adjacency lists with heaps from the heapq module keeps the code readable while remaining efficient enough for graphs with thousands of vertices. In C, careful memory management and inline Dijkstra calls give the best throughput for production deployments handling the road networks of cities like Perth, Darwin, or Hobart.