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
