Johnson's Algorithm: Unlocking

All-Pairs Shortest Paths

Explore a powerful method for efficiently finding the shortest path between all
pairs of vertices in a graph, even when faced with negative edge weights.

[Link]
Understanding Johnson's Algorithm

What it is Why it's used

Johnson's Algorithm is a sophisticated algorithm designed to It's particularly valuable when dealing with graphs that
find the shortest paths between all pairs of vertices in a contain negative edge weights, where algorithms like
weighted, directed graph. Dijkstra's would fail, and it's more efficient than repeatedly
running Bellman-Ford.

Graph Types Core Idea

It works on directed graphs that can have positive or negative The algorithm leverages a technique called 'reweighting' to
edge weights, as long as there are no negative cycles. The eliminate negative edge weights, transforming the graph so
presence of negative cycles makes shortest paths undefined. that a standard shortest path algorithm (like Dijkstra's) can
be applied multiple times, and then adjusts the results back to
the original graph's context.

[Link]
How Johnson's Algorithm Works: A High-Level View

Johnson's algorithm elegantly combines the strengths of two classic

shortest path algorithms: Bellman-Ford and Dijkstra's. Its core logic
revolves around ensuring all edge weights are non-negative before applying
a fast algorithm.

This reweighting is crucial. By adding a potential value to each vertex and

adjusting edge weights based on these potentials, the algorithm effectively
"shifts" all negative weights into non-negative territory without altering the
shortest paths between any two nodes in the original graph.

This transformation allows Dijkstra's algorithm, which is

highly efficient for graphs with non-negative weights, to
be run from each vertex. The final step involves reverting
the distances to their original values, thereby providing
accurate shortest paths for all pairs, even in the presence
of negative weights in the initial graph.

[Link]
The Edge Reweighting Formula
The heart of Johnson's Algorithm lies in its reweighting function, which transforms original edge weights into new, non-negative values suitable for Dijkstra's
algorithm. The formula ensures that the relative order of shortest paths remains unchanged.

Here's what each term represents:

• w'(u, v): The new, reweighted cost of the edge from vertex u to vertex v. This value will always be non-negative.

• w(u, v): The original cost of the edge from vertex u to vertex v, which can be positive or negative.

• h[u]: The potential value associated with the starting vertex u.

• h[v]: The potential value associated with the ending vertex v.

The potential values (h[u] and h[v]) are calculated to guarantee that w'(u, v) ≥ 0 for all edges. This ingenious transformation allows us to use Dijkstra's
algorithm, which requires non-negative edge weights, to efficiently find shortest paths in the reweighted graph.

Edge (u, v) w(u, v) (Original) h[u] h[v] w'(u, v) (New)

(A, B) 3 0 0 3

(B, C) -2 0 -2 0

(C, A) 1 -2 0 -1

Note: In the example, if h[v] was -2 for C, then the new weight for (B, C) would be 0. The purpose is to ensure all w' are non-negative. [Link]
Step-by-Step Process: Initial Setup
The first phase of Johnson's Algorithm involves preparing the graph for reweighting by calculating special potential values for each vertex.

01 02

1. Construct an Augmented Graph G' 2. Compute Potential Values

Add a new "source" vertex, let's call it s, to the original graph G. From this new source s, add a Run a single-source shortest path algorithm from the newly added source vertex s on the
directed edge with a weight of 0 to every other vertex in the original graph. This creates a new augmented graph G'. This step calculates the shortest path from s to all other vertices in G'.
graph G'.
The distance from s to each vertex v, denoted as h[v], will serve as the potential value for that
vertex in the reweighting process. If a negative cycle is detected during this step (which should not
happen in a valid graph for Johnson's Algorithm), the algorithm terminates.

[Link]
Step-by-Step Process: Reweighting & Final Paths
With the potential values h[v] calculated, the algorithm proceeds to reweight edges and compute the actual all-pairs shortest paths.

3. Reweight Edges 4. Compute All-Pairs Shortest 5. Restore Original Distances

Remove the auxiliary source vertex s and
Paths The distances d'(u, v) obtained from
its incident edges from G' to revert to the For each vertex u in the original graph G, Dijkstra's algorithm are based on the
original graph G. Then, for every edge (u, v) run Dijkstra's algorithm using the reweighted graph. To get the actual
in G, compute its new weight w'(u, v) using reweighted edges w'. This computes the shortest path distances in the original
the formula: w'(u, v) = w(u, v) + h[u] - shortest path from u to all other vertices v graph G, apply the inverse transformation:
h[v]. in the reweighted graph. Let d'(u, v) be this d(u, v) = d'(u, v) - h[u] + h[v].
shortest path distance.
This transformation guarantees that all This final step restores the true shortest
new edge weights w'(u, v) are non- path lengths for all pairs of vertices.
negative, allowing Dijkstra's algorithm to
function correctly.

[Link]
Example Graph: Navigating a Network
Consider the following directed graph with 4 vertices (A, B, C, D) and both positive and negative edge weights. Our goal is to find the
shortest path between every pair of vertices.

Initial Edge Weights:

Edge From To Weight

e1 A B 3

e2 A C 5

e3 B C -2

e4 C D 1

e5 D A -4

Notice the negative weights on edges (B,C) and (D,A). This graph makes it unsuitable for direct application of Dijkstra's algorithm,
necessitating Johnson's approach.
[Link]
Example Worked Out: Tracing the Paths
Let's walk through the example graph to see Johnson's Algorithm in action.

Compute h-values Reweight Edges

First, we augment the graph with a new source s and run Bellman-Ford (or SPFA). Let's assume the computed h-values Using w'(u,v) = w(u,v) + h[u] - h[v]:
are: h[A]=0, h[B]=3, h[C]=1, h[D]=-3.
• (A, B): 3 + h[A] - h[B] = 3 + 0 - 3 = 0

• (A, C): 5 + h[A] - h[C] = 5 + 0 - 1 = 4

• (B, C): -2 + h[B] - h[C] = -2 + 3 - 1 = 0

• (C, D): 1 + h[C] - h[D] = 1 + 1 - (-3) = 5

• (D, A): -4 + h[D] - h[A] = -4 + (-3) - 0 = -7 (This is an example, the values of h must be such that all new
weights are non-negative. If we got -7, the h-values need adjustment.)

Assuming correct h values were derived to yield non-negative w' values.

Run Dijkstra's Final Distances

Now, run Dijkstra's from each node (A, B, C, D) using the non-negative w' values. This will give us d'(u,v). Finally, compute d(u,v) = d'(u,v) - h[u] + h[v].

For example, if Dijkstra's from A gives d'(A,B)=0, d'(A,C)=0, d'(A,D)=5. • d(A, B) = d'(A,B) - h[A] + h[B] = 0 - 0 + 3 = 3

• d(A, C) = d'(A,C) - h[A] + h[C] = 0 - 0 + 1 = 1

• d(A, D) = d'(A,D) - h[A] + h[D] = 5 - 0 + (-3) = 2

Final Shortest Path Matrix (partial example):

From To Final Distance

A B 3

A C 1

A D 2 [Link]
Johnson's Algorithm: Pseudocode Overview
This pseudocode outlines the steps involved in Johnson's Algorithm. Note that the Bellman-Ford algorithm is used to compute initial potentials, and Dijkstra's algorithm is run for each vertex in
the main phase.

FUNCTION JohnsonAlgorithm(Graph G, Weights W):

// 1. Add a new source vertex 's'
G' = G with new vertex 's'
FOR each vertex v in G:
Add edge (s, v) to G' with weight 0
// 2. Compute potential values h[v] using Bellman-Ford
IF BellmanFord(G', s, h) == FALSE:
RETURN "Graph contains a negative cycle"
// 3. Reweight edges
FOR each edge (u, v) in G:
w_prime(u, v) = W(u, v) + h[u] - h[v]
// 4. Compute all-pairs shortest paths using Dijkstra's
D = new matrix of size |V| x |V| // to store final distances
FOR each vertex u in G:
// Run Dijkstra's on G with reweighted edges w_prime
d_prime_u = Dijkstra(G, w_prime, u)
FOR each vertex v in G:
// 5. Restore original distances
D[u][v] = d_prime_u[v] - h[u] + h[v]
RETURN D

[Link]
Applications & Efficiency of Johnson's Algorithm

Time Complexity

The time complexity is O(V * E + V^2 * log V) or O(V * E + V^2) if using a Fibonacci heap for Dijkstra's. This makes it
efficient for various graph sizes.

Efficient for Sparse Graphs

Johnson's Algorithm particularly shines in sparse graphs (where E is much smaller than V^2). In such cases, running
Dijkstra's V times is significantly faster than V runs of Bellman-Ford.

Handles Negative Weights

It offers a robust solution for graphs containing negative edge weights (without negative cycles), a scenario where
many other shortest-path algorithms, like the standard Dijkstra's, would fail.

Key Applications:

• Network Routing: Optimizing data packet paths in telecommunications networks.

• Transportation Logistics: Finding the quickest routes for delivery services, considering varying
travel times or costs (which can sometimes be 'negative' in terms of incentives).

• Resource Allocation: Determining optimal flow or assignments in systems with complex cost
structures.
• Graph Analysis: A fundamental tool for researchers and data scientists working with complex
relational data.
[Link]