Johnson's Algorithm

📂 Graph Algorithms 📅 Updated: Oct 2025 ⏱️ 8 min read ✅ Peer-Reviewed

Overview

Johnson's algorithm is an efficient method for finding the shortest paths between all pairs of vertices in a weighted directed graph. It was published by Donald B. Johnson in 1977 and is particularly advantageous for sparse graphs, outperforming the Floyd–Warshall algorithm when the number of edges \(E\) is significantly smaller than \(V^2\).

Unlike Floyd–Warshall, which has a fixed time complexity of \(O(V^3)\) regardless of graph density, Johnson's algorithm leverages the Bellman–Ford algorithm for edge reweighting followed by multiple executions of Dijkstra's algorithm, achieving a complexity of \(O(V(E + V \log V))\) with a Fibonacci heap.

Key Advantage: Handles graphs with negative edge weights (as long as there are no negative cycles) while maintaining superior performance on sparse networks.

How It Works

The core insight behind Johnson's algorithm is the technique of potential functions (or reweighting), which transforms negative edge weights into non-negative values without altering the shortest path structure.

Step-by-Step Process

Add a new vertex \(s\) with zero-weight edges to every vertex in the graph.
Run Bellman–Ford from \(s\) to detect negative cycles. If none exist, extract the shortest distances \(h(v)\) from \(s\) to each vertex.
Reweight all edges using the potential function: \(w'(u, v) = w(u, v) + h(u) - h(v)\). This guarantees \(w'(u, v) \geq 0\).
Remove vertex \(s\) and the added edges.
Run Dijkstra's algorithm from every vertex \(v\) using the reweighted edges \(w'\).
Adjust distances back to original scale: \(\delta(u, v) = \delta'(u, v) - h(u) + h(v)\).

Pseudocode

// Johnson(u, G)
function Johnson(G)
    // 1. Add auxiliary vertex s
    V ← G.vertices()
    create new vertex s
    for each v in V do
        G.add_edge(s, v, 0)
    // 2. Bellman-Ford from s
    h ← BellmanFord(G, s)
    if h.has_negative_cycle() then
        return "Negative cycle detected"
    // 3. Reweight edges
    for each (u, v) in G.edges() do
        G.weight(u, v) ← G.weight(u, v) + h(u) - h(v)
    // 4. Remove s
    G.remove_vertex(s)
    // 5. Run Dijkstra from each vertex
    D ← new Matrix(|V|, |V|)
    for each v in V do
        D[v] ← Dijkstra(G, v)
    // 6. Restore original distances
    for each v in V do
        for each u in V do
            D[v][u] ← D[v][u] - h(v) + h(u)
    return D

Time & Space Complexity

Component	Complexity	Notes
Bellman–Ford	`O(VE)`	Detects cycles & computes potentials
Reweighting	`O(E)`	Linear edge traversal
Dijkstra (V times)	`O(V(E + V log V))`	With Fibonacci heap
Total	`O(V(E + V log V))`	Dominant term
Space	`O(V²)`	To store all-pairs distances

For dense graphs where \(E \approx V^2\), this degrades to \(O(V^3 \log V)\), making Floyd–Warshall preferable. For sparse graphs \((E \ll V^2)\), Johnson's algorithm is significantly faster.

Applications

Network Routing: Optimizing packet paths in telecommunications with dynamic or asymmetric costs.
Operations Research: Transportation logistics, supply chain optimization, and scheduling problems.
Computer Graphics & Physics: Collision detection graphs and force simulation networks.
Machine Learning: Graph neural networks requiring efficient all-pairs similarity computations.
Game Development: Pathfinding in complex environments with variable terrain costs.

Comparison with Alternatives

Johnson's algorithm occupies a unique niche between single-source and all-pairs shortest path algorithms:

vs Floyd–Warshall: Johnson wins on sparse graphs with negative edges; Floyd–Warshall is simpler and faster on dense graphs.
vs Repeated Dijkstra: Standard Dijkstra cannot handle negative edges. Johnson's reweighting enables Dijkstra's efficiency safely.
vs Repeated Bellman–Ford: Running Bellman–Ford \(V\) times yields \(O(V^2E)\), which is worse than Johnson's approach for most practical cases.

References & Further Reading

Johnson, D. B. (1977). "Efficient Algorithms for Shortest Paths in Sparse Networks". Journal of the ACM, 24(1), 1-13.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press. (Section 25.3)
Klein, P. N. (1987). "A Faster Fully Parallel Shortest Path Algorithm". Journal of Algorithms, 8(1), 27-36.
CLRS Exercise 25.3-4: Implementation details and heap optimization strategies.