Johnson Potential Reweighting

Theory

The core idea of Johnson's algorithm is to reweight the edges of the graph such that all weights become non-negative. This enables the use of Dijkstra's algorithm, which is significantly faster than Bellman-Ford, to compute the shortest paths.

The algorithm introduces a new super-source vertex connected to all existing vertices with zero-weight edges. It then runs the Bellman-Ford algorithm from this new vertex to compute a potential function h(v) for each vertex v. If a negative cycle is detected during this step, the algorithm terminates, as shortest paths are undefined.

Otherwise, the edges are reweighted using the formula:w_new(u, v) = w(u, v) + h(u) - h(v). The triangle inequality established by the shortest path potentials guarantees that w_new(u, v) >= 0 for all edges.

Finally, Dijkstra's algorithm is run from each vertex using the non-negative weights w_new. The true shortest path distance d(u, v) is then recovered via the inverse transformation:d(u, v) = d_new(u, v) - h(u) + h(v).

Worked Example

Consider the "Negative edges" graph from the interactive module with vertices 0, 1, 2, 3 and the following edges:

• 0 → 1 (w=1)
• 0 → 2 (w=4)
• 1 → 2 (w=-2)
• 2 → 3 (w=2)
• 1 → 3 (w=5)
• 3 → 1 (w=1)

We want to find the shortest path from Source 0 to Target 3. First, we compute the potentials h by running Bellman-Ford from a virtual super-source. The initial potentials are h = [0, 0, 0, 0].

The Bellman-Ford passes will update the potentials as follows:

Pass 1: h[1] = min(h[1], h[0] + 1) = 0 h[2] = min(h[2], h[0] + 4) = 0 h[2] = min(h[2], h[1] - 2) = -2 (Changed) h[3] = min(h[3], h[2] + 2) = 0 h[3] = min(h[3], h[1] + 5) = 0 h[1] = min(h[1], h[3] + 1) = 0 Resulting h = [0, 0, -2, 0]

Next, we compute the reweighted edges w_new(u, v) = w(u, v) + h(u) - h(v):

• 0 → 1: 1 + 0 - 0 = 1
• 0 → 2: 4 + 0 - (-2) = 6
• 1 → 2: -2 + 0 - (-2) = 0
• 2 → 3: 2 + (-2) - 0 = 0
• 1 → 3: 5 + 0 - 0 = 5
• 3 → 1: 1 + 0 - 0 = 1

The minimum reweighted edge is 0. Running Dijkstra on the reweighted graph from Source 0 to Target 3 gives:

1. Start at 0 (dist=0)
2. Relax 0 → 1: dist[1] = 0 + 1 = 1
3. Relax 0 → 2: dist[2] = 0 + 6 = 6
4. Visit 1 (dist=1)
5. Relax 1 → 2: dist[2] = min(6, 1 + 0) = 1
6. Relax 1 → 3: dist[3] = 1 + 5 = 6
7. Visit 2 (dist=1)
8. Relax 2 → 3: dist[3] = min(6, 1 + 0) = 1
9. Visit 3 (dist=1)

The reweighted distance is 1. Finally, we recover the true distance:d(0, 3) = d_new(0, 3) - h(0) + h(3) = 1 - 0 + 0 = 1.

Experiment

You can interact with the Johnson Potential Reweighting module to see how the graph topology and edge weights affect the potentials and reweighted values.

1. Select "Negative cycle" in the Graph dropdown. Observe that the globally detected cycle immediately halts further calculation and changes the result Status to "Negative cycle".
2. Select "Disconnected" in the Graph dropdown. Notice that the vertices' potential arrays still update since the super-source can reach them, but the Source-to-Target distances display as Unreachable.

Limitations

While Johnson's algorithm is more efficient than running Bellman-Ford from every vertex for sparse graphs, it still requires an initial Bellman-Ford pass. This pass takes O(V * E) time. If the graph contains a negative-weight cycle, the algorithm cannot compute shortest paths and must abort.

For dense graphs where E is close to V^2, the overall time complexity of Johnson's algorithm, O(V^2 * log(V) + V * E), is asymptotically the same or slightly worse than Floyd-Warshall, which takes O(V^3) time.

References

You can learn more about Johnson's algorithm in the following reference:

• NetworkX: Johnson's algorithm