Wait, What?
A graph can contain negative edges and still become safe for Dijkstra—without changing which paths are shortest.
Johnson’s algorithm is a masterclass in algorithm composition. It solves the all-pairs shortest-path problem on weighted directed graphs that may contain negative edge weights, provided there is no negative-weight cycle. Its central move is not to invent a new shortest-path routine from scratch. Instead, it computes a potential for every vertex, reweights every edge so that all transformed weights are non-negative, then runs Dijkstra from each source.
For learners, this is a powerful step from “I know Bellman–Ford” and “I know Dijkstra” to I can combine algorithms by proving a transformation preserves the answer. That is professional algorithmic reasoning.
Quick Answer
Learn Johnson’s algorithm in this order: all-pairs shortest paths → why negative edges break ordinary Dijkstra → super-source → Bellman–Ford potentials → reweighting formula → proof of non-negative transformed edges → proof that shortest-path order is preserved → repeated Dijkstra → convert distances back → complexity and graph-density trade-offs. The heart of the method is the potential function, not the loop structure.
1. First Name the Exact Job
Given a weighted directed graph G=(V,E), the all-pairs shortest-path problem asks for the shortest distance from every vertex s to every vertex t. If all edge weights are non-negative, running Dijkstra once from every source is a natural option. If edges may be negative, ordinary Dijkstra is not valid because a vertex that appears settled can later be improved through a negative edge.
Floyd–Warshall can handle negative edges and computes all pairs in Θ(V³), but Johnson’s algorithm is often attractive for sparse graphs, where E is much smaller than V².
2. Negative Cycles Change the Meaning of “Shortest”
Before worrying about speed, check whether finite shortest paths even exist. If a reachable cycle has negative total weight, travelling around that cycle repeatedly can reduce path cost without bound. The distance is then not a finite minimum.
Johnson’s algorithm uses Bellman–Ford at the beginning partly because Bellman–Ford can detect this failure state. If a negative cycle exists, the algorithm must stop rather than pretend a finite all-pairs answer exists.
3. Add a Super-Source
Create a new vertex q. Add a directed edge q→v of weight 0 for every original vertex v.
for each v in V:
add edge (q, v) with weight 0Now every original vertex is reachable from q. Run Bellman–Ford from q and define:
h(v) = shortest distance from q to vThese h-values are called potentials. They are not the final all-pairs distances. They are the numbers that make the reweighting work.
4. The Reweighting Formula
For every original edge (u,v), define a new edge weight:
w'(u,v) = w(u,v) + h(u) - h(v)At first this looks like a clever trick. It becomes much easier to remember after proving the two properties Johnson needs.
5. Why Every Reweighted Edge Is Non-Negative
Because h(v) is a shortest distance from q, taking a shortest route to u and then edge (u,v) cannot beat h(v). Therefore:
h(v) ≤ h(u) + w(u,v)Rearrange:
w(u,v) + h(u) - h(v) ≥ 0But that left-hand side is exactly w'(u,v). So all transformed edges are non-negative. Dijkstra is now allowed to operate.
6. Why Reweighting Does Not Change Which Path Wins
Take any path from s to t:
s = v0 → v1 → v2 → ... → vk = tIts reweighted cost is:
Σ [w(vi,vi+1) + h(vi) - h(vi+1)]All the interior potential terms cancel. What remains is:
original path cost + h(s) - h(t)Every s→t path receives the same additive shift h(s)-h(t). Therefore, if path A was cheaper than path B before reweighting, it remains cheaper afterwards. The identity of the shortest path is preserved.
This telescoping cancellation is the conceptual centre of the entire algorithm.
7. Run Dijkstra From Every Source
After reweighting, remove the temporary super-source q. Run Dijkstra from each original vertex s using w’. This produces transformed shortest distances d'(s,t).
for each source s in V:
d'[s] = Dijkstra(G, w', s)Finally convert them back:
d(s,t) = d'(s,t) - h(s) + h(t)This simply reverses the additive shift introduced by reweighting.
8. Full Pseudocode
Johnson(G):
add new vertex q
for each v in G.V:
add edge q → v with weight 0
h = BellmanFord(G, q)
if BellmanFord found a negative cycle:
fail: finite APSP is not defined
for each original edge (u,v):
w'(u,v) = w(u,v) + h(u) - h(v)
remove q and its edges
for each source s:
d' = Dijkstra(G, w', s)
for each target t reachable from s:
d[s,t] = d'[t] - h(s) + h(t)
return d9. Trace a Small Example Before Coding
Use a four-vertex directed graph with one negative edge but no negative cycle. Build a table with these columns:
- vertex
- Bellman–Ford potential h(v)
- original outgoing edge weight
- reweighted edge weight
- Dijkstra distance under w’
- restored original distance
The learning goal is not merely to get the final matrix. Verify three things by hand: every transformed edge is non-negative; two competing paths from the same source to target preserve their ordering; and restoring with -h(s)+h(t) gives the original shortest distance.
10. Why Adding a Constant to Every Edge Does Not Work
A tempting mistake is to find the most negative edge and add a large constant C to all edges. This can change shortest paths because different paths may use different numbers of edges. A three-edge path receives 3C while a five-edge path receives 5C.
Johnson’s potential transformation is different: every complete s→t path receives exactly h(s)-h(t), regardless of how many edges it contains.
11. Complexity: Where Johnson Wins
Bellman–Ford costs O(VE). With a binary-heap style Dijkstra, running Dijkstra from every source gives a common bound of O(VE + V² log V), with details depending on the priority-queue implementation and graph representation. Current NetworkX documentation states the complexity as O(nm + n² log n).
The key comparison is structural, not merely symbolic. Floyd–Warshall touches a V×V×V dynamic-programming state space. Johnson performs one Bellman–Ford pass plus repeated sparse-graph searches. For a dense graph, Floyd–Warshall may be simpler and competitive. For a sparse graph with negative edges but no negative cycle, Johnson can be a better fit.
12. Distances, Paths and Predecessors
An implementation must define whether it returns only distances or reconstructible paths. If paths are required, each Dijkstra run needs predecessor information, or the API must retain enough state to reconstruct the vertex sequence.
Do not confuse transformed distances with transformed paths. Reweighting changes path costs but preserves which path is shortest between a fixed pair.
13. Unreachable Vertices Need Explicit Semantics
The super-source makes every vertex reachable from q, but original vertices may still be mutually unreachable. A production implementation should represent these distances explicitly—commonly as infinity, absence from a map, or a documented sentinel.
Never let an unreachable target accidentally enter the distance-restoration arithmetic as if it had a finite d’.
14. Floating-Point Weights Need Care
The algebra is exact on paper. Floating-point arithmetic can introduce tiny negative transformed values such as -1e-15 when theory predicts zero. Whether to clamp such values depends on the numerical contract; silently changing weights is not always safe.
Professional implementations document numeric types, tolerances and whether exact integer/rational weights are expected.
15. Potentials Are a Transferable Idea
Johnson’s h-values are not just a trick for one algorithm. Potential functions appear in reduced-cost reasoning, min-cost flow, primal–dual methods and amortized analysis. The transferable pattern is:
- Choose a transformation.
- Prove it moves the problem into a friendlier domain.
- Prove the transformation preserves the quantity you care about.
- Use a faster or simpler subroutine in the transformed domain.
- Map the answer back.
16. Common Failure States
- Running Dijkstra directly on negative edges.
- Forgetting to detect negative cycles before continuing.
- Using w'(u,v)=w(u,v)+h(v)-h(u), reversing the potential signs.
- Believing edge reweighting must preserve individual edge costs rather than path ordering.
- Adding one constant to all edges and assuming shortest paths survive.
- Forgetting to convert d’ back to original distances.
- Comparing Johnson with Floyd–Warshall without considering graph density.
- Ignoring unreachable pairs or numeric precision.
17. Practice Ladder: Beginner to Professional
- Beginner: explain why Dijkstra can fail with a negative edge.
- Foundation: run Bellman–Ford from a super-source and compute h(v) by hand.
- Intermediate: reweight every edge and verify w’≥0.
- Advanced: prove the telescoping path-shift identity and restore distances correctly.
- Professional: benchmark Johnson against Floyd–Warshall and repeated Bellman–Ford on sparse and dense graphs; test negative cycles, disconnected components and large weights.
- Transfer: identify another algorithm where a potential or reduced-cost transformation makes a harder subproblem easier.
18. A Better Way to Study Johnson’s Algorithm
Do not passively reread the pseudocode. Use a worked example, then cover the formulas and reconstruct the subgoals: make every vertex reachable → obtain feasible potentials → make edges non-negative → preserve path ordering → exploit Dijkstra → undo the transformation. Programming-education research on subgoal-labelled worked examples suggests that explicitly naming these purposes can reduce unproductive cognitive load. Algorithm-visualisation research also supports active prediction: pause before each Bellman–Ford relaxation or Dijkstra extraction and predict the next state.
Learning Hall Boundary
This article owns Johnson’s algorithm for all-pairs shortest paths on sparse weighted graphs with negative edges but no negative cycles. It does not replace the existing shortest-path foundations, Dijkstra instruction, Bellman–Ford instruction, Floyd–Warshall material, graph-theory foundations, MindOS learning-process articles, Bolt measurement jobs or Student/Studying Interface workflow content.
Evidence Boundary
Donald B. Johnson introduced the sparse-network shortest-path method in Journal of the ACM 24(1), 1977, pp. 1–13, DOI 10.1145/321992.321993. Current NetworkX 3.6.1 documentation describes Johnson’s method as Bellman–Ford reweighting followed by Dijkstra and lists a complexity of O(nm+n² log n): NetworkX Johnson documentation. The teaching sequence also draws on programming-education evidence for subgoal-labelled worked examples and algorithm visualisation, including ACM SIGCSE work on worked examples for dynamic programming and recent algorithm-visualisation research.
Professional rule: you understand Johnson’s algorithm when you can prove both why every transformed edge is non-negative and why every s→t path receives the same additive shift—before you write the Dijkstra loop.
