Johnson's Algorithm

A Bit of History

Donald B. Johnson published "Efficient Algorithms for Shortest Paths in Sparse Networks" in 1977, solving a specific gap left open by earlier deep dives in this series: Floyd-Warshall handles negative edges but runs in \(O(V^3)\) regardless of how sparse the graph is, while Dijkstra's algorithm is much faster on sparse graphs but breaks entirely in the presence of negative edge weights. Johnson's algorithm was previewed briefly in Part 10 and finally gets its own full treatment here, completing this series' all-pairs shortest path story.

Working Principle: Reweighting

The core idea is to transform the graph's edge weights so that they all become non-negative — allowing Dijkstra to be run safely from every vertex — without changing which paths are shortest. The algorithm proceeds in three stages:

1. Add an auxiliary vertex \(q\) connected to every other vertex with a zero-weight edge, and run Bellman-Ford (from an earlier deep dive) from \(q\) to compute \(h(v)\), the shortest distance from \(q\) to every vertex \(v\) (this also detects any negative cycle, in which case the algorithm reports failure and stops).
2. Reweight every edge \((u,v)\) with original weight \(w(u,v)\) to a new weight \(w'(u,v) = w(u,v) + h(u) - h(v)\) — guaranteed to be non-negative for every edge (a consequence of the triangle-inequality-like property Bellman-Ford's shortest distances satisfy).
3. Run Dijkstra from every vertex using these new non-negative weights \(w'\), then convert each computed shortest-path distance back to the original weighting via \(d(u,v) = d'(u,v) - h(u) + h(v)\).

Worked Example

Consider a graph with one negative edge, say weight \(-2\) from \(B\) to \(C\), among otherwise positive edges. Bellman-Ford from the auxiliary vertex \(q\) computes \(h\)-values for every vertex; reweighting every edge using the formula above transforms the \(-2\) edge into a non-negative value (while every other edge's weight also shifts, but stays non-negative too) — the graph is now safe for Dijkstra. Running Dijkstra once from each vertex on this reweighted graph, then converting each result back with the inverse formula, produces the exact same all-pairs shortest distances Floyd-Warshall would have computed directly, but considerably faster on a sparse graph.

Why Reweighting Preserves Shortest Paths

For any path \(P = v_0 \to v_1 \to \cdots \to v_k\), the reweighted total cost is:

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

since every intermediate \(h(v_i)\) term appears once with a \(+\) sign and once with a \(-\) sign, canceling out (a telescoping sum). Since \(h(v_0) - h(v_k)\) is the same fixed constant for every path from \(v_0\) to \(v_k\) regardless of which intermediate vertices it uses, the path with minimum \(w(P)\) is guaranteed to also have minimum \(w'(P)\) — reweighting never changes which path is shortest, only shifts every path's cost by the same fixed amount.

Complexity Analysis

Bellman-Ford runs once in \(O(VE)\); Dijkstra (with a binary or Fibonacci heap) runs once per vertex, \(V\) times, at \(O(E \log V)\) each:

$$\text{Time: } O(VE + V^2 \log V) \qquad \text{vs. Floyd-Warshall's } O(V^3)$$

For sparse graphs (where \(E \ll V^2\), common in road networks and many real-world graphs), Johnson's algorithm is dramatically faster than Floyd-Warshall's dense-graph-oriented \(O(V^3)\) — precisely the "efficient algorithms for sparse networks" promised in the title of Johnson's original 1977 paper.

Implementation

import heapq

def johnsons_algorithm(n, edges):
    """
    n: number of vertices. edges: list of (u, v, weight) directed edges.
    Returns an n x n matrix of shortest distances, or None if a negative cycle exists.
    """
    INF = float('inf')
    adj = [[] for _ in range(n)]
    for u, v, w in edges:
        adj[u].append((v, w))

    # Step 1: Bellman-Ford from an auxiliary vertex connected to everyone at weight 0
    h = [0] * n  # equivalent to Bellman-Ford's result, since q->v edges all have weight 0
    for _ in range(n - 1):
        for u, v, w in edges:
            if h[u] + w < h[v]:
                h[v] = h[u] + w
    for u, v, w in edges:
        if h[u] + w < h[v]:
            return None  # negative cycle detected

    # Step 2: Reweight every edge
    reweighted_adj = [[] for _ in range(n)]
    for u, v, w in edges:
        reweighted_adj[u].append((v, w + h[u] - h[v]))

    # Step 3: Run Dijkstra from every vertex, then convert back
    dist = [[INF] * n for _ in range(n)]
    for src in range(n):
        d = [INF] * n
        d[src] = 0
        pq = [(0, src)]
        while pq:
            cur_d, u = heapq.heappop(pq)
            if cur_d > d[u]:
                continue
            for v, w in reweighted_adj[u]:
                if d[u] + w < d[v]:
                    d[v] = d[u] + w
                    heapq.heappush(pq, (d[v], v))
        for v in range(n):
            if d[v] < INF:
                dist[src][v] = d[v] - h[src] + h[v]

    return dist

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)]
result = johnsons_algorithm(5, edges)
for row in result:
    print(row)

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

const int INF = numeric_limits<int>::max();

bool johnsonsAlgorithm(int n, vector<tuple<int,int,int>>& edges, vector<vector<int>>& dist) {
    vector<long long> h(n, 0);
    for (int iter = 0; iter < n - 1; iter++) {
        for (auto& [u, v, w] : edges) {
            if (h[u] != INF && h[u] + w < h[v]) h[v] = h[u] + w;
        }
    }
    for (auto& [u, v, w] : edges) {
        if (h[u] + w < h[v]) return false;  // negative cycle
    }

    vector<vector<pair<int,int>>> adj(n);
    for (auto& [u, v, w] : edges) {
        adj[u].push_back({v, (int)(w + h[u] - h[v])});
    }

    dist.assign(n, vector<int>(n, INF));
    for (int src = 0; src < n; src++) {
        vector<int> d(n, INF);
        d[src] = 0;
        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
        pq.push({0, src});
        while (!pq.empty()) {
            auto [curD, u] = pq.top(); pq.pop();
            if (curD > d[u]) continue;
            for (auto& [v, w] : adj[u]) {
                if (d[u] + w < d[v]) { d[v] = d[u] + w; pq.push({d[v], v}); }
            }
        }
        for (int v = 0; v < n; v++) {
            if (d[v] < INF) dist[src][v] = d[v] - (int)h[src] + (int)h[v];
        }
    }
    return true;
}

int main() {
    vector<tuple<int,int,int>> 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<int>> dist;
    johnsonsAlgorithm(5, edges, dist);
    for (auto& row : dist) {
        for (int d : row) cout << d << " ";
        cout << endl;
    }
    return 0;
}

import java.util.*;

class Johnsons {
    static int[][] solve(int n, int[][] edges) {  // edges[i] = {u, v, w}
        final int INF = Integer.MAX_VALUE / 2;
        long[] h = new long[n];

        for (int iter = 0; iter < n - 1; iter++) {
            for (int[] e : edges) {
                if (h[e[0]] + e[2] < h[e[1]]) h[e[1]] = h[e[0]] + e[2];
            }
        }
        for (int[] e : edges) {
            if (h[e[0]] + e[2] < h[e[1]]) return null;  // negative cycle
        }

        List<List<int[]>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) {
            int newW = (int)(e[2] + h[e[0]] - h[e[1]]);
            adj.get(e[0]).add(new int[]{e[1], newW});
        }

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

        for (int src = 0; src < n; src++) {
            int[] d = new int[n];
            Arrays.fill(d, INF);
            d[src] = 0;
            PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
            pq.add(new int[]{0, src});
            while (!pq.isEmpty()) {
                int[] cur = pq.poll();
                int curD = cur[0], u = cur[1];
                if (curD > d[u]) continue;
                for (int[] edge : adj.get(u)) {
                    int v = edge[0], w = edge[1];
                    if (d[u] + w < d[v]) { d[v] = d[u] + w; pq.add(new int[]{d[v], v}); }
                }
            }
            for (int v = 0; v < n; v++) {
                if (d[v] < INF) dist[src][v] = (int)(d[v] - h[src] + h[v]);
            }
        }
        return dist;
    }

    public static void main(String[] args) {
        int[][] 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}
        };
        int[][] dist = solve(5, edges);
        for (int[] row : dist) System.out.println(Arrays.toString(row));
    }
}

Real-World Applications

Exercises

1. Verify the telescoping-sum argument by hand: pick a 3-edge path and confirm that the reweighted total cost equals the original cost plus \(h(v_0) - h(v_k)\).
2. Explain why Johnson's algorithm needs to detect negative cycles during its Bellman-Ford step, and what "no well-defined shortest path" would mean if one existed.
3. Compare Johnson's algorithm's complexity to Floyd-Warshall's on a graph with \(V=1000\) vertices and \(E=2000\) edges (a genuinely sparse graph) — which is asymptotically faster here, and by roughly how much?
4. Challenge: Modify the implementation to also reconstruct and print the actual shortest path (not just its distance) between a specific pair of vertices.

Limitations