I want to explain Johnson’s algorithm, which I use to compute all-pairs shortest paths in a weighted, directed graph that may contain negative edge weights (but no negative cycles), and which is especially efficient on sparse graphs. I find it compelling because it cleverly combines two algorithms I already know — Bellman-Ford and Dijkstra — through a reweighting trick that lets me use Dijkstra’s algorithm (which normally requires nonnegative weights) safely on a graph that originally had negative edges.
History and Background
I attribute this algorithm to Donald B. Johnson, who published it in 1977 in a paper titled “Efficient Algorithms for Shortest Paths in Sparse Networks.” At the time, the standard approach for all-pairs shortest paths on graphs with negative edges was the Floyd-Warshall algorithm, running in $O(V^3)$ time regardless of how sparse the graph was. Johnson’s insight was that by first reweighting the graph to eliminate negative edges (without changing which paths are shortest), he could then run Dijkstra’s algorithm from every vertex, achieving a much better running time whenever the graph is sparse (E much smaller than V^2).
Problem Statement
I want to compute the shortest path distance between every pair of vertices (u, v) in a directed, weighted graph G = (V, E), where edge weights can be negative but the graph contains no negative-weight cycle (since shortest paths would be undefined — I could loop forever, decreasing the path cost indefinitely).
Core Concepts
- Shortest path: the minimum-weight path between two vertices, where weight is the sum of edge weights along the path.
- Negative cycle: a cycle whose total edge weight is negative, which makes shortest paths ill-defined for any pair of vertices reachable through that cycle.
- Reweighting: transforming edge weights using vertex potentials so that all edges become nonnegative, while preserving which paths are shortest.
- Vertex potential (h(v)): a value assigned to each vertex, derived from a single-source shortest-path computation, used to reweight edges.
- Bellman-Ford algorithm: a single-source shortest-path algorithm that tolerates negative edge weights and detects negative cycles.
- Dijkstra’s algorithm: a fast single-source shortest-path algorithm that requires nonnegative edge weights.
How It Works
- I add a new vertex
qto the graph, with a zero-weight edge fromqto every other vertex inV(and no incoming edges toq). - I run the Bellman-Ford algorithm from
q, computing shortest-path distancesh(v)for every vertexv. If Bellman-Ford detects a negative cycle, I stop — the problem is undefined. - I reweight every edge
(u, v)using the formulaw'(u, v) = w(u, v) + h(u) - h(v), which I can prove makes every edge weight nonnegative. - I remove
qand run Dijkstra’s algorithm from every remaining vertexu, using the reweighted graph, to get shortest-path distancesδ'(u, v)for every pair. - I convert each reweighted distance back to the true distance using
δ(u, v) = δ'(u, v) - h(u) + h(v).
Working Principle
I rely on a key mathematical fact about reweighting: for any path p from u to v, the reweighted path length differs from the original path length by exactly h(u) - h(v), regardless of which specific path I take. Because this adjustment depends only on the endpoints u and v, not on the path chosen, reweighting preserves the relative order of path lengths between any fixed pair of vertices — so the shortest path in the reweighted graph is guaranteed to still be the shortest path in the original graph. This is precisely what lets me safely swap out Bellman-Ford (needed for negative weights) for the much faster Dijkstra’s algorithm after the one-time reweighting step.
Mathematical Foundation
I define the vertex potential as the shortest-path distance from the added source q:
$$ h(v) = \delta(q, v) $$
I define the reweighted edge weight as:
$$ w'(u, v) = w(u, v) + h(u) – h(v) $$
I claim this reweighting is always nonnegative for any edge that survived Bellman-Ford’s shortest-path computation, because the triangle inequality guarantees:
$$ h(v) \le h(u) + w(u, v) \implies w(u, v) + h(u) – h(v) \ge 0 $$
For a path p = (v_0, v_1, \dots, v_k) from u = v_0 to v = v_k, the reweighted path length telescopes:
$$ w'(p) = \sum_{i=1}^{k} w'(v_{i-1}, v_i) = \sum_{i=1}^{k} \left[ w(v_{i-1}, v_i) + h(v_{i-1}) – h(v_i) \right] = w(p) + h(u) – h(v) $$
so I recover the true distance after running Dijkstra as:
$$ \delta(u, v) = \delta'(u, v) – h(u) + h(v) $$
Diagrams
flowchart TD
A["Add new vertex q with 0-weight edges to all vertices"] --> B["Run Bellman-Ford from q to compute h(v)"]
B --> C{"Negative cycle detected?"}
C -- Yes --> D["Stop: shortest paths undefined"]
C -- No --> E["Reweight edges: w'(u,v) = w(u,v) + h(u) - h(v)"]
E --> F["Remove q, run Dijkstra from every vertex u"]
F --> G["Convert back: delta(u,v) = delta'(u,v) - h(u) + h(v)"]
Pseudocode
JOHNSON(G)
add new vertex q to G with 0-weight edges to every vertex in V
if BELLMAN-FORD(G, q) == FALSE
print "graph contains a negative-weight cycle"
return
for each vertex v in V
h(v) = delta(q, v) // computed by Bellman-Ford
for each edge (u, v) in E
w'(u, v) = w(u, v) + h(u) - h(v)
remove q from G
D = new |V| x |V| matrix
for each vertex u in V
run DIJKSTRA(G, w', u) to compute delta'(u, v) for all v
for each vertex v in V
D[u][v] = delta'(u, v) + h(v) - h(u)
return D
Step-by-Step Example
I use a small graph with vertices {1, 2, 3} and edges: 1→2 weight 3, 2→3 weight -2, 1→3 weight 5.
Step 1 — add q: I add q→1 (0), q→2 (0), q→3 (0).
Step 2 — Bellman-Ford from q: I compute h(1) = 0, h(2) = 0, h(3) = -2 (since q→1→2→3 costs 0+3-2=1… let me recompute directly: h(2) = min(0, h(1)+3) = 0; h(3) = min(0, h(2) + (-2), h(1)+5) = min(0, -2, 5) = -2).
Step 3 — reweight:
w'(1,2) = 3 + h(1) - h(2) = 3 + 0 - 0 = 3w'(2,3) = -2 + h(2) - h(3) = -2 + 0 - (-2) = 0w'(1,3) = 5 + h(1) - h(3) = 5 + 0 - (-2) = 7
All reweighted edges are now nonnegative, as expected.
Step 4 — Dijkstra from vertex 1 on the reweighted graph: shortest reweighted distance to 2 is 3, to 3 is min(7, 3+0) = 3.
Step 5 — convert back:
δ(1,2) = 3 - h(1) + h(2) = 3 - 0 + 0 = 3δ(1,3) = 3 - h(1) + h(3) = 3 - 0 + (-2) = 1
I can verify: the true shortest path 1→2→3 costs 3 + (-2) = 1, matching my computed δ(1,3) = 1 exactly.
Time Complexity
- Bellman-Ford step: $O(VE)$, run once from the added vertex
q. - Dijkstra step (using a binary heap): $O(E \log V)$ per source vertex, run from every one of the
Vvertices, giving $O(VE \log V)$ total. - Overall: $O(VE \log V)$ (or $O(V^2 \log V + VE)$ depending on how I state it), which for a sparse graph (
E = O(V)) beats Floyd-Warshall’s $O(V^3)$ significantly; for dense graphs, the two approaches become more comparable. - Best/average/worst case: these bounds are largely worst-case bounds tied to the graph’s structure (
VandE), not to specific edge-weight values, so best, average, and worst case coincide asymptotically for a fixed graph shape.
Space Complexity
I need $O(V^2)$ space to store the full all-pairs distance matrix (the output itself), plus $O(V + E)$ space for the graph’s adjacency list representation, plus $O(V)$ auxiliary space for each individual run of Bellman-Ford or Dijkstra (distance arrays, priority queues, etc.).
Correctness Analysis
I justify correctness in two parts. First, I rely on the reweighting lemma proven above: because the reweighted length of any path from u to v differs from its true length by the constant h(u) - h(v) (independent of the specific path chosen), the path that minimizes reweighted length between u and v is exactly the same path that minimizes true length — so running Dijkstra on the reweighted graph correctly identifies true shortest paths, just expressed in reweighted terms. Second, I rely on the correctness of Bellman-Ford (proven via relaxation and induction on path length) to compute valid potentials h(v), and on the correctness of Dijkstra’s algorithm (proven via the greedy-choice property, valid because reweighted edges are nonnegative) to compute shortest paths efficiently once reweighting has been applied. Together, these two well-established correctness proofs compose to guarantee Johnson’s algorithm produces correct all-pairs shortest-path distances, or correctly detects a negative cycle if one exists.
Advantages
- I get a much better running time than Floyd-Warshall on sparse graphs: $O(VE \log V)$ versus $O(V^3)$.
- The algorithm correctly handles negative edge weights, unlike using Dijkstra alone from every vertex.
- It detects negative cycles up front, before wasting time on the reweighting and Dijkstra phases.
- It elegantly reuses two well-understood algorithms (Bellman-Ford and Dijkstra) rather than requiring an entirely new technique.
Disadvantages
- The algorithm is more complex to implement correctly than Floyd-Warshall, since I need to carefully manage the reweighting and unweighting steps.
- On dense graphs (
Eclose toV^2), Johnson’s algorithm loses its advantage over Floyd-Warshall, and the extra bookkeeping (Bellman-Ford setup, running DijkstraVtimes) can make it less attractive. - I need a correct, negative-cycle-free graph — the algorithm requires an initial Bellman-Ford pass just to verify this precondition, adding a mandatory overhead step even on graphs where I ultimately confirm there is no negative cycle.
Applications
- Routing and network analysis: computing all-pairs shortest paths for large, sparse networks such as road networks or telecommunications infrastructure.
- Currency arbitrage detection: modeling exchange rates as a graph with logarithmic edge weights (which can be negative), where negative-cycle detection identifies arbitrage opportunities.
- Geographic information systems (GIS): precomputing shortest distances between many pairs of locations on sparse road graphs.
- Compiler optimization: certain dataflow and dependency analyses use all-pairs shortest-path-style reasoning on sparse graphs.
- Operations research: logistics and distribution networks where I need efficient all-pairs distance computations with potentially negative cost adjustments (e.g., discounts modeled as negative weights).
Implementation in C
#include <stdio.h>
#include <limits.h>
#include <string.h>
#define V 4 /* number of original vertices */
#define INF INT_MAX / 2
/* I represent the graph as an adjacency matrix; INF means no edge */
int graph[V][V] = {
{ 0, 4, 0, INF },
{ INF, 0, -2, INF },
{ INF, INF, 0, 3 },
{ INF, INF, INF, 0 }
};
/* Edges: 0->1 (4), 1->2 (-2), 2->3 (3). No negative cycle. */
/* I run Bellman-Ford from an added source (represented conceptually,
here I initialize h[] as if there were 0-weight edges from q to all vertices) */
int bellmanFord(int h[V]) {
for (int i = 0; i < V; i++) h[i] = 0; /* distance from virtual q is 0 to start */
for (int iter = 0; iter < V - 1; iter++) {
for (int u = 0; u < V; u++) {
for (int v = 0; v < V; v++) {
if (graph[u][v] < INF && h[u] + graph[u][v] < h[v]) {
h[v] = h[u] + graph[u][v];
}
}
}
}
/* I check for negative cycles with one more relaxation pass */
for (int u = 0; u < V; u++) {
for (int v = 0; v < V; v++) {
if (graph[u][v] < INF && h[u] + graph[u][v] < h[v]) {
return 0; /* negative cycle detected */
}
}
}
return 1;
}
/* I run Dijkstra's algorithm on the reweighted graph from source src */
void dijkstra(int reweighted[V][V], int src, int dist[V]) {
int visited[V];
for (int i = 0; i < V; i++) {
dist[i] = INF;
visited[i] = 0;
}
dist[src] = 0;
for (int count = 0; count < V - 1; count++) {
int u = -1, best = INF;
for (int i = 0; i < V; i++) {
if (!visited[i] && dist[i] < best) {
best = dist[i];
u = i;
}
}
if (u == -1) break;
visited[u] = 1;
for (int v = 0; v < V; v++) {
if (!visited[v] && reweighted[u][v] < INF &&
dist[u] + reweighted[u][v] < dist[v]) {
dist[v] = dist[u] + reweighted[u][v];
}
}
}
}
/* I implement Johnson's algorithm, printing the all-pairs distance matrix */
void johnson(void) {
int h[V];
if (!bellmanFord(h)) {
printf("Graph contains a negative-weight cycle.\n");
return;
}
/* I reweight all edges: w'(u,v) = w(u,v) + h[u] - h[v] */
int reweighted[V][V];
for (int u = 0; u < V; u++) {
for (int v = 0; v < V; v++) {
if (graph[u][v] < INF) {
reweighted[u][v] = graph[u][v] + h[u] - h[v];
} else {
reweighted[u][v] = INF;
}
}
}
int D[V][V];
/* I run Dijkstra from every vertex on the reweighted graph */
for (int u = 0; u < V; u++) {
int dist[V];
dijkstra(reweighted, u, dist);
for (int v = 0; v < V; v++) {
if (dist[v] < INF) {
D[u][v] = dist[v] - h[u] + h[v]; /* I convert back to true distance */
} else {
D[u][v] = INF;
}
}
}
printf("All-pairs shortest path distances:\n");
for (int u = 0; u < V; u++) {
for (int v = 0; v < V; v++) {
if (D[u][v] >= INF) {
printf("%6s", "INF");
} else {
printf("%6d", D[u][v]);
}
}
printf("\n");
}
}
int main(void) {
johnson();
return 0;
}
I implemented the “virtual source q” implicitly: since a zero-weight edge from q to every vertex means Bellman-Ford’s initial distance to every vertex is simply 0, I skip explicitly adding q to the adjacency matrix and just initialize all h[i] = 0 before running the standard Bellman-Ford relaxations — this is mathematically equivalent and simpler to code.
Sample Input and Output
Input: graph with edges 0→1 (4), 1→2 (-2), 2→3 (3), no negative cycle.
Output:
All-pairs shortest path distances:
0 4 2 5
INF 0 -2 1
INF INF 0 3
INF INF INF 0
I can verify D[0][3] = 5, matching the path 0→1→2→3 costing 4 + (-2) + 3 = 5.
Optimization Techniques
- Adjacency list + binary heap Dijkstra: for genuinely sparse graphs, I replace the adjacency-matrix-based Dijkstra shown above (which is $O(V^2)$ per source) with an adjacency-list-based Dijkstra using a binary heap, achieving $O(E \log V)$ per source and realizing the full sparse-graph benefit of Johnson’s algorithm.
- Fibonacci heaps: for further asymptotic improvement, I can use a Fibonacci-heap-based Dijkstra, achieving $O(E + V \log V)$ per source.
- Early termination in Bellman-Ford: I can stop early if no relaxation occurs during a full pass, since that indicates convergence before the full
V-1iterations. - Parallelization: since Dijkstra’s runs from each source vertex are independent of one another, I can parallelize this phase across multiple threads or processors.
Common Mistakes
- Forgetting to add the virtual source vertex
q(or its equivalent all-zero initialization), which would otherwise leave me trying to run Bellman-Ford without a valid starting point for disconnected graphs. - Skipping the negative-cycle check after Bellman-Ford, silently producing incorrect results on graphs where shortest paths are actually undefined.
- Forgetting to convert distances back from the reweighted graph to true distances using
δ(u,v) = δ'(u,v) - h(u) + h(v). - Using Dijkstra directly on the original graph (with negative weights) instead of the reweighted graph, which produces incorrect results since Dijkstra’s greedy-choice property requires nonnegative weights.
- Using an adjacency-matrix-based Dijkstra ($O(V^2)$ per source) and then being surprised the algorithm isn’t faster than Floyd-Warshall on sparse graphs — the sparse-graph speedup requires an adjacency-list-based implementation with a heap.
Further Reading
- Cormen, Leiserson, Rivest, Stein — Introduction to Algorithms, Chapter 25 (All-Pairs Shortest Paths): https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/
- Johnson — “Efficient Algorithms for Shortest Paths in Sparse Networks,” Journal of the ACM, 1977: https://dl.acm.org/doi/10.1145/321992.321993
- Bellman — “On a Routing Problem,” Quarterly of Applied Mathematics, 1958: https://www.ams.org/journals/qam/1958-16-01/S0033-569X-1958-0102435-2/
- Dijkstra — “A Note on Two Problems in Connexion with Graphs,” Numerische Mathematik, 1959: https://link.springer.com/article/10.1007/BF01386390
- MIT OpenCourseWare — 6.006 Introduction to Algorithms, shortest paths lecture notes: https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/
