Johnson's Algorithm
Johnson computes all-pairs shortest paths in a sparse directed graph with negative edges by reweighting once, then running Dijkstra from every vertex.
The sparse all-pairs problem
Floyd–Warshall gives O(V³) all-pairs shortest paths and is attractive for dense graphs. Repeating Bellman–Ford is too slow on sparse graphs with negative edges. Johnson combines one Bellman–Ford pass with V heap-based Dijkstra runs, giving O(VE+V(E+V)log V).
The graph may contain negative edges but no negative cycle. If a negative cycle exists, shortest distances through it have no finite value because repeated traversal lowers path weight without bound; Johnson must detect and report this before any Dijkstra run.
- Designed for sparse directed graphs
- Negative edges are allowed
- Negative cycles abort the algorithm
Super-source and potentials
Add a new source q with zero-weight edges to every original vertex and run Bellman–Ford from q. Let h(v)=δ(q,v). Every vertex is reachable, so all potentials are finite unless a negative cycle exists anywhere in the graph—not merely in one original component.
The shortest-path inequality h(v)≤h(u)+w(u,v) rearranges to w(u,v)+h(u)−h(v)≥0. Define this expression as the reweighted edge w'. That causation is why Dijkstra becomes legal; arbitrary offsets would not guarantee nonnegative edges.
- Zero edges make every component reachable
- Potentials are Bellman–Ford distances
- Triangle inequality proves nonnegative reweights
Terms, operations, and practical uses
Reweighting
- Super-sourceSuper-source is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
- Vertex potentialVertex potential is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
- Reweighted edgeReweighted edge is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
Shortest paths
- Bellman–FordBellman–Ford is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
- Repeated DijkstraRepeated Dijkstra is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
- Endpoint correctionEndpoint correction is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
Safety
- Negative cycleNegative cycle is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
- Telescoping sumTelescoping sum is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
- Infinite distanceInfinite distance is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
Johnson reweights before repeated Dijkstra
import heapq
edges=[(0,1,2),(0,2,4),(1,2,-1)];n=3;h=[0]*n
for _ in range(n-1):
for u,v,w in edges:h[v]=min(h[v],h[u]+w)
adj=[[] for _ in range(n)]
for u,v,w in edges:adj[u].append((v,w+h[u]-h[v]))
d=[10**9]*n;d[0]=0;q=[(0,0)]
while q:
x,u=heapq.heappop(q)
if x!=d[u]:continue
for v,w in adj[u]:
if x+w<d[v]:d[v]=x+w;heapq.heappush(q,(d[v],v))
answer=d[2]-h[0]+h[2]
print("A→C shortest:",answer)#include <algorithm>
#include <array>
#include <cstring>
#include <functional>
#include <iostream>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;
int main() {
vector<array<int,3>> edges={{{0,1,2},{0,2,4},{1,2,-1}}};
vector<int> h(3),d(3,1e9);
for(int i=1;i<3;i++) for(auto [u,v,w]:edges) h[v]=min(h[v],h[u]+w);
vector<vector<pair<int,int>>> g(3);
for(auto [u,v,w]:edges) g[u].push_back({v,w+h[u]-h[v]});
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
d[0]=0;
q.push({0,0});
while(!q.empty()) {
auto [du,u]=q.top();
q.pop();
if(du!=d[u]) continue;
for(auto [v,w]:g[u]) if(du+w<d[v]) d[v]=du+w,q.push({d[v],v});
}
cout << "A→C shortest: " << d[2]-h[0]+h[2] << '\n';
}import java.util.*;
class Main {
public static void main(String[] args) {
int[][] e={{0,1,2},{0,2,4},{1,2,-1}};
int[] h=new int[3],d={1_000_000_000,1_000_000_000,1_000_000_000};
for(int i=1;i<3;i++) for(int[] x:e) h[x[1]]=Math.min(h[x[1]],h[x[0]]+x[2]);
List<int[]>[] g=new List[3];
for(int i=0;i<3;i++) g[i]=new ArrayList<>();
for(int[] x:e) g[x[0]].add(new int[]{x[1],x[2]+h[x[0]]-h[x[1]]});
PriorityQueue<int[]> q=new PriorityQueue<>(Comparator.comparingInt(a->a[0]));
d[0]=0;
q.add(new int[]{0,0});
while(!q.isEmpty()) {
int[] s=q.remove();
if(s[0]!=d[s[1]]) continue;
for(int[] x:g[s[1]]) if(s[0]+x[1]<d[x[0]]) {
d[x[0]]=s[0]+x[1];
q.add(new int[]{d[x[0]],x[0]});
}
}
System.out.println("A→C shortest: "+(d[2]-h[0]+h[2]));
}
}Step through it
Running on A→B 2, A→C 4, B→C −1
Why shortest paths are preserved
Along a path u=v₀,…,vₖ=v, potential terms telescope: the reweighted path cost equals original cost+h(u)−h(v). Every path with the same endpoints receives the same additive offset, so their ordering and shortest choice are unchanged.
After Dijkstra returns d'(u,v), recover the original distance as d(u,v)=d'(u,v)−h(u)+h(v). Forgetting this correction publishes distances in the transformed graph, not the input graph. Unreachable pairs remain infinity.
- Potentials telescope along a path
- Equal endpoints receive equal offsets
- Undo potentials on every reported pair
Execution pipeline
Build the augmented edge list, run Bellman–Ford for V relaxation rounds including the super-source, and abort on an extra-pass improvement. Remove q conceptually, compute w' for each original edge, then run Dijkstra from each original vertex and fill one result row.
Use wide numeric types: adding potentials to weights can overflow even when final distances fit. Preserve infinity during correction rather than performing arithmetic on a sentinel. The output itself has Θ(V²) entries, so no all-pairs algorithm can use less than quadratic output space when materializing the matrix.
- Bellman–Ford precedes every Dijkstra
- Correct only finite distances
- The distance matrix costs Θ(V²) space
Choosing Johnson or Floyd–Warshall
Johnson benefits sparse graphs because E is far below V². Floyd–Warshall has simpler loops, naturally handles dense adjacency matrices, and can reconstruct paths with a next matrix. Repeated Dijkstra alone is enough if every edge is already nonnegative.
Test disconnected graphs, zero and negative edges, a negative cycle in a separate component, parallel edges, and corrected distances that are negative. Verify that every reweighted edge is nonnegative and compare small matrices against Floyd–Warshall as an independent oracle.
- Sparsity drives the choice
- Already nonnegative graphs need no potentials
- Cross-check small cases with Floyd–Warshall
Path reconstruction and numeric discipline
To reconstruct routes, retain each Dijkstra predecessor row; potentials change weights but not which path is shortest between fixed endpoints. Convert only the reported distance, not predecessor identities. If several equal routes exist, heap and adjacency order choose one valid parent tree.
Use a sentinel well below overflow and guard it before addition in Bellman–Ford and Dijkstra. A super-source is temporary and must not appear in the output matrix. Validate diagonal zeros, triangle inequalities for finite results, and negative-cycle rejection on a cycle unreachable from any chosen original source.
A useful invariant during reweighting is that every transformed path from u to v differs from its original cost by exactly h(u)−h(v), regardless of how many edges it contains. Test this directly on several competing paths, not only individual edges. If the implementation stores an adjacency matrix, parallel edges must first be reduced to their minimum weight; an adjacency list can retain them and let relaxation choose. Johnson computes distances, not transitive closure: unreachable pairs stay unreachable after potentials are applied. For route queries, reconstruct predecessors in transformed space and report the same vertex sequence with the corrected original cost.
- Predecessors survive reweighting
- Never add to infinity sentinels
- Remove the temporary source from outputs