*87*

# Johnson’s Algorithm

The problem is to find the shortest path between every pair of vertices in a given weighted directed graph and weight may be negative. Using Johnson’s Algorithm, we can find all pairs shortest path in O (V^{2} log ? V+VE ) time. Johnson’s Algorithm uses both Dijkstra’s Algorithm and Bellman-Ford Algorithm.

Johnson’s Algorithm uses the technique of **“reweighting.”** If all edge weights w in a graph G = (V, E) are nonnegative, we can find the shortest paths between all pairs of vertices by running Dijkstra’s Algorithm once from each vertex. If G has negative – weight edges, we compute a new – set of non – negative edge weights that allows us to use the same method. The new set of edges weight w must satisfy two essential properties:

- For all pair of vertices u, v ∈ V, the shortest path from u to v using weight function w is also the shortest path from u to v using weight function w.
- For all edges (u, v), the new weight w (u, v) is nonnegative.

Given a weighted, directed graph G = (V, E) with weight function w: E→R and let h: v→R be any function mapping vertices to a real number.

For each edge (u, v) ∈ E define

Where h (u) = label of u

h (v) = label of v

JOHNSON (G)1. Compute G' where V [G'] = V[G] ∪ {S} and E [G'] = E [G] ∪ {(s, v): v ∈ V [G] } 2. If BELLMAN-FORD (G',w, s) = FALSE then "input graph contains a negative weight cycle" else for each vertex v ∈ V [G'] do h (v) ← δ(s, v) Computed by Bellman-Ford algorithm for each edge (u, v) ∈ E[G'] do w (u, v) ← w (u, v) + h (u) - h (v) for each edge u ∈ V [G] do run DIJKSTRA (G, w, u) to compute δ (u, v) for all v ∈ V [G] for each vertex v ∈ V [G] do d_{uv}← δ (u, v) + h (v) - h (u) Return D.

**Example:**

**Step1:** Take any source vertex’s’ outside the graph and make distance from’s’ to every vertex ‘0’.

**Step2:** Apply Bellman-Ford Algorithm and calculate minimum weight on each vertex.

**Step3:** w (a, b) = w (a, b) + h (a) – h (b)

= -3 + (-1) – (-4)

= 0

w (b, a) = w (b, a) + h (b) – h (a)

= 5 + (-4) – (-1)

= 2

w (b, c) = w (b, c) + h (b) – h (c)

w (b, c) = 3 + (-4) – (-1)

= 0

w (c, a) = w (c, a) + h (c) – h (a)

w (c, a) = 1 + (-1) – (-1)

= 1

w (d, c) = w (d, c) + h (d) – h (c)

w (d, c) = 4 + 0 – (-1)

= 5

w (d, a) = w (d, a) + h (d) – h (a)

w (d, a) = -1 + 0 – (-1)

= 0

w (a, d) = w (a, d) + h (a) – h (d)

w (a, d) = 2 + (-1) – 0 = 1

**Step 4:** Now all edge weights are positive and now we can apply Dijkstra’s Algorithm on each vertex and make a matrix corresponds to each vertex in a graph

**Case 1:** ‘a’ as a source vertex

**Case 2:** ‘b’ as a source vertex

**Case 3:** ‘c’ as a source vertex

**Case4:**‘d’ as source vertex

**Step5:**

d_{uv} ← δ (u, v) + h (v) – h (u)

d (a, a) = 0 + (-1) – (-1) = 0

d (a, b) = 0 + (-4) – (-1) = -3

d (a, c) = 0 + (-1) – (-1) = 0

d (a, d) = 1 + (0) – (-1) = 2

d (b, a) = 1 + (-1) – (-4) = 4

d (b, b) = 0 + (-4) – (-4) = 0

d (c, a) = 1 + (-1) – (-1) = 1

d (c, b) = 1 + (-4) – (-1) = -2

d (c, c) = 0

d (c, d) = 2 + (0) – (-1) = 3

d (d, a) = 0 + (-1) – (0) = -1

d (d, b) = 0 + (-4) – (0) = -4

d (d, c) = 0 + (-1) – (0) = -1

d (d, d) = 0