Scribd
Upload
11 views

Johnson Algorithm

Explaination of Johnson algorithm

Uploaded by

Shrishu Ranjan
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
11 views

Johnson Algorithm

Explaination of Johnson algorithm

Uploaded by

Shrishu Ranjan
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 7

Johnson Algorithm

All pair shortest path for sparse graph.


Will NOT work correctly if there are negative weight cycles in the graph

Steps to calculate:
Given graph G

1. Compute G ′

Add a augmented new node source s connected to every other node with edge weight = 0

2. Apply Bellman-Ford on G ′
The cost is stored in respective node (yellow) after applying the bellman ford to get shortest path wrt to s

Negative Weight Cycle

Will NOT work correctly if there are negative weight cycles in the graph.

Even though the reweighting is meant to eliminate negative weights, negative weight cycles can lead to
issues where the shortest path lengths cannot be properly computed or defined, as you can keep
reducing the path length indefinitely by repeatedly traversing the cycle.

3. Update the edges to non-negative value


For each edge (u, v) update the new cost as

w(u,
^ v) = w(u, v) + h(u) − h(v)
Similarly applying to all edge we get

4. Remove the Augmented Node

5.1 Apply Dijkstra and Write the cost of the shortest path first from a starting
node.
Let the starting node be a and shortest path from a to each node is stored after applying Dijkstra

Here value inside any node is written as (x / y)

x := Dijkstra Shortest path from starting node to current node


y := Used to restore edge that was modified earlier
Suppose if we need to calculate the value for node c

So the value inside node c will be (2 / − 3)

Similarly filling all the value using the formula we get

^
duv = δ(u, v) + h(v) − h(u)
Restore Edge

So for the shortest path for a given node, we get back the original edge weight

5.2 Repeat the above step considering every node as starting point

You might also like