Offensive Security Researcher & Quantum Cryptography Analyst

Johnson’s Algorithm for Sparse Graphs: Complete Explanation and Implementation

Abdul Wahab Junaid
Johnson's Algorithm for Sparse Graphs

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

How It Works

  1. I add a new vertex q to the graph, with a zero-weight edge from q to every other vertex in V (and no incoming edges to q).
  2. I run the Bellman-Ford algorithm from q, computing shortest-path distances h(v) for every vertex v. If Bellman-Ford detects a negative cycle, I stop — the problem is undefined.
  3. I reweight every edge (u, v) using the formula w'(u, v) = w(u, v) + h(u) - h(v), which I can prove makes every edge weight nonnegative.
  4. I remove q and run Dijkstra’s algorithm from every remaining vertex u, using the reweighted graph, to get shortest-path distances δ'(u, v) for every pair.
  5. 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:

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:

I can verify: the true shortest path 1→2→3 costs 3 + (-2) = 1, matching my computed δ(1,3) = 1 exactly.

Time Complexity

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

Disadvantages

Applications

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

Common Mistakes

Further Reading

Exit mobile version