Implementing the Johnson’s Algorithm for Efficient All-pairs Shortest Path Computations

Introduction to the All-Pairs Shortest Path Problem

In graph theory and network analysis, computing the shortest path between every pair of vertices is a fundamental challenge with wide practical applications. Whether you are optimizing a delivery network, analyzing social connections, or designing an internet routing protocol, the all-pairs shortest path (APSP) problem provides the complete distance matrix required for many algorithms. The classic solution for dense graphs is the Floyd–Warshall algorithm, but when graphs are sparse or contain negative edge weights, more efficient approaches exist. Johnson’s Algorithm stands out as an elegant hybrid method that combines the strengths of Bellman–Ford and Dijkstra to solve the APSP problem efficiently on graphs with negative weights (as long as no negative cycles exist).

This article provides a detailed, production-ready guide to implementing Johnson’s Algorithm. We will cover its theoretical foundation, step-by-step implementation, pseudocode, a complete code example in Python, complexity analysis, and comparisons with other methods. By the end, you will understand not only how the algorithm works but also when and why to choose it over alternatives.

Prerequisites and Core Graph Concepts

Before diving into the algorithm, we must define the underlying model. A graph G = (V, E) consists of a set of vertices (nodes) and edges connecting them. Each edge can have a weight representing cost, distance, or time. Weights can be positive, zero, or negative. In real-world problems, negative weights appear in contexts such as economic transactions, reward systems, or data structures where “shortest” might mean “most profitable.”

A negative cycle is any cycle whose total weight is negative. If a negative cycle exists, the concept of “shortest path” breaks down because you could traverse the cycle repeatedly to make the path arbitrarily short. Johnson’s Algorithm requires that the input graph has no negative cycles; the Bellman–Ford step will detect them and abort.

The algorithm uses two classic subroutines:

Bellman–Ford: solves the single-source shortest path problem even with negative weights, in O(|V|·|E|) time.
Dijkstra: solves the single-source shortest path problem for non-negative weights in O(|E| + |V| log |V|) time using a priority queue.

Johnson’s genius was to reweight the edges so that Dijkstra can be applied to every source node, while preserving the correctness of the shortest paths.

Step-by-Step Explanation of Johnson’s Algorithm

The algorithm proceeds in five clear steps. We will describe each step, its purpose, and the mathematical justification.

Step 1: Add a Super-Source Vertex

Introduce a new vertex s that is not part of the original graph. Connect s to every original vertex v ∈ V with an edge of weight 0. This auxiliary graph has |V|+1 vertices. The zero-weight edges ensure that we can compute initial distances without distorting any existing path costs.

Step 2: Run Bellman–Ford from the Super-Source

Execute the Bellman–Ford algorithm with s as the source. The result is an array h[v] representing the shortest distance from s to each vertex v. These values are called vertex potentials. If Bellman–Ford detects a negative cycle reachable from s, the algorithm terminates because the original graph also contains a negative cycle (since all edges from s have zero weight, any cycle in the original graph remains).

Step 3: Reweight All Edges

For every original edge (u, v) with weight w(u, v), compute a new weight:

w'(u, v) = w(u, v) + h(u) - h(v)

This transformation guarantees that all new edge weights are non-negative. Why? The Bellman–Ford step ensures that h(v) ≤ h(u) + w(u, v), or equivalently w(u, v) + h(u) - h(v) ≥ 0. The reweighting does not change the relative ordering of paths: for any path from a to b, the sum of reweighted edges equals the original path length plus h(a) - h(b). Therefore, the shortest path between a and b in the reweighted graph corresponds to the shortest path in the original graph.

Step 4: Run Dijkstra from Each Vertex

Now that all edge weights are non-negative, we can run Dijkstra’s algorithm independently from each vertex u on the reweighted graph. This produces the shortest distance d'(u, v) for every pair (u, v) in the reweighted graph.

Step 5: Adjust Distances Back to Original Weights

Because the reweighting shifted distances, we must reverse the transformation:

d(u, v) = d'(u, v) + h(v) - h(u)

Now d(u, v) is the true shortest path distance in the original graph. No further computation is needed.

Pseudocode for Johnson’s Algorithm

The following pseudocode captures the algorithm in a clear, implementable form:

function jhonson(G):
    // G is a weighted graph (V, E) with no negative cycles
    V = G.vertices
    E = G.edges
    // Step 1: add super-source
    s = new_vertex()
    for each v in V:
        add_edge(s, v, 0)
    // Step 2: compute potentials with Bellman-Ford
    h = bellman_ford(G ∪ {s}, s)
    if h contains detection of negative cycle:
        return error "Graph has a negative cycle"
    // Step 3: reweight edges
    G' = empty graph with vertices V
    for each edge (u, v, w) in E:
        w' = w + h[u] - h[v]
        add_edge(G', u, v, w')
    // Step 4: run Dijkstra from each vertex on G'
    D = 2D array filled with infinity
    for each u in V:
        dist_u = dijkstra(G', u)
        for each v in V:
            D[u][v] = dist_u[v]
    // Step 5: adjust distances
    for each u in V:
        for each v in V:
            D[u][v] = D[u][v] + h[v] - h[u]
    return D

Python Implementation Example

Below is a practical Python implementation that uses a simple adjacency list representation and a min-heap for Dijkstra. This code is intended for educational purposes and can be adapted for production systems. (Note: the code uses standard libraries and follows Python 3 conventions.)

import heapq
from typing import Dict, List, Tuple, Optional

INF = float('inf')

def bellman_ford(graph: Dict[int, List[Tuple[int, float]]], src: int, n: int) -> Tuple[Optional[List[float]], bool]:
    """Return (dist, has_negative_cycle)"""
    dist = [INF] * n
    dist[src] = 0.0
    for _ in range(n - 1):
        for u in range(n):
            for v, w in graph.get(u, []):
                if dist[u] != INF and dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w
    # Check for negative cycles
    for u in range(n):
        for v, w in graph.get(u, []):
            if dist[u] != INF and dist[u] + w < dist[v]:
                return None, True  # Negative cycle
    return dist, False

def dijkstra(graph: Dict[int, List[Tuple[int, float]]], src: int, n: int) -> List[float]:
    dist = [INF] * n
    dist[src] = 0.0
    pq = [(0.0, src)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, w in graph.get(u, []):
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))
    return dist

def johnson(graph: Dict[int, List[Tuple[int, float]]], n: int) -> Optional[List[List[float]]]:
    """Return distance matrix or None if negative cycle"""
    # Step 1: add super-source (index n)
    super_src = n
    # Build extended graph for Bellman-Ford
    extended_graph = {i: list(edges) for i, edges in graph.items()}
    extended_graph[super_src] = [(v, 0.0) for v in range(n)]
    # Step 2: potentials
    h, neg_cycle = bellman_ford(extended_graph, super_src, n+1)
    if neg_cycle or h is None:
        return None
    # Step 3: reweight edges
    reweighted_graph = {i: [] for i in range(n)}
    for u in range(n):
        for v, w in graph.get(u, []):
            w_new = w + h[u] - h[v]
            reweighted_graph[u].append((v, w_new))
    # Step 4: run Dijkstra from each vertex
    dist_matrix = [[INF]*n for _ in range(n)]
    for u in range(n):
        dist_u = dijkstra(reweighted_graph, u, n)
        # Step 5: adjust
        for v in range(n):
            if dist_u[v] != INF:
                dist_matrix[u][v] = dist_u[v] + h[v] - h[u]
            else:
                dist_matrix[u][v] = INF
    return dist_matrix

In a real application, you would read the graph from a file or API. The function returns the distance matrix where dist_matrix[u][v] is the shortest distance from u to v. If the graph contains a negative cycle, the function returns None and an error can be raised.

Time Complexity Analysis

Johnson’s Algorithm is efficient for sparse graphs. Let us break down the complexity:

Bellman–Ford: O(|V|·|E|) for the super-source graph, which includes the original |E| edges plus |V| zero-weight edges. So O(|V|·|E|).
Reweighting: Iterates over each edge once: O(|E|).
Dijkstra (repeated): Called |V| times. Each run using a binary heap takes O(|E| + |V| log |V|). Therefore total O(|V|·|E| + |V|² log |V|).
Final adjustment: O(|V|²) to compute the final distances.

Overall, the complexity is O(|V|·|E| + |V|² log |V|). In the worst case of a dense graph where |E| = Θ(|V|²), this becomes O(|V|³), the same as Floyd–Warshall. However, on sparse graphs (|E| = O(|V|)) the running time is O(|V|² log |V|), which is significantly better.

Comparison with Other All-Pairs Algorithms

Choosing the right APSP algorithm depends on the graph’s density and the presence of negative weights.

Algorithm	Time Complexity	Handles Negative Weights?	Best Use Case
Floyd–Warshall	O(\|V\|³)	Yes (no negative cycles)	Dense graphs, simplicity
Repeated Dijkstra (naive)	O(\|V\|·(\|E\| + \|V\| log \|V\|))	No	Sparse graphs with non-negative weights
Repeated Bellman–Ford	O(\|V\|²·\|E\|)	Yes	Dense graphs with negatives (rarely used)
Johnson’s Algorithm	O(\|V\|·\|E\| + \|V\|² log \|V\|)	Yes (no negative cycles)	Sparse graphs with negative edge weights

Johnson’s Algorithm offers the best of both worlds: it tolerates negative weights and is faster than Floyd–Warshall when the graph is sparse. For many real-world networks, which are sparse and often contain negative costs (e.g., arbitrage opportunities in currency exchange), Johnson’s is the algorithm of choice.

When to Use Johnson’s Algorithm

Johnson’s Algorithm is not a one-size-fits-all solution. Use it when:

The graph has negative edge weights but no negative cycles (detected during the Bellman–Ford phase).
The graph is sparse: |E| ≪ |V|². For dense graphs, Floyd–Warshall may be simpler and equally fast in practice.
You need the entire distance matrix (all pairs). For a single pair, use Bellman–Ford or Dijkstra with heuristics.
Memory is not a critical constraint: storing the matrix O(|V|²) is required.

If the graph contains negative cycles, no algorithm can give meaningful shortest path results. In such cases, use Bellman–Ford or a cycle detection algorithm to identify the offending edges.

Applications in Industry and Research

Johnson’s Algorithm appears in many fields:

Network Routing: Design of routing protocols that must handle varying link costs (including negative costs from discounts or rebalanced loads).
Currency Arbitrage: Finding profit cycles in foreign exchange markets by modeling exchange rates as negative logarithms.
Transportation Logistics: Computing shortest paths between multiple depots and destinations when roads have tolls (positive) or subsidies (negative).
Bioinformatics: Analyzing metabolic networks where reactions have associated free energies.
Social Network Analysis: Measuring centrality or distance in weighted graphs where relationships can have negative affinities.

For a deeper theoretical treatment, refer to the original paper by Donald B. Johnson (1977) “Efficient Algorithms for Shortest Paths in Sparse Networks,” or the classic textbook Introduction to Algorithms (CLRS). Interactive visualizations of the algorithm are available at VisuAlgo to help solidify the step-by-step process.

Conclusion

Johnson’s Algorithm remains a cornerstone of advanced graph algorithm design. By cleverly combining Bellman–Ford and Dijkstra with a potential function reweighting, it solves the all-pairs shortest path problem on sparse graphs with negative edge weights in near-quadratic time. Understanding its mechanics gives you a powerful tool for analyzing networks where costs are not always positive. The Python implementation provided here can serve as a foundation for integrating the algorithm into your own projects, whether in research, education, or production.

When you encounter a graph problem with many vertices but relatively few edges, and the weights can be negative, reach for Johnson’s Algorithm. It is efficient, correct, and conceptually elegant.

For further study, explore the Wikipedia article on Johnson’s Algorithm or examine competitive programming implementations to see how the algorithm is optimized in practice.