All-pairs shortest paths using Johnson’s algorithm is used to find shortest paths between every pair of vertices in a given weighted directed Graph and weights might be negative, we have discussed this problem in http://wikistack.com/all-pair-shortest-path-floyd-warshall-algorithm/ . Johnson’s algorithm used to solve shortest path problem when graph is sparse weighted directed. An sparse graph is the graph where number of edges are usually much less. Here much less means much more edges are possible in given graph.

Johnson’s algorithm  works when graph does not  contain negative edge weight cycles.

Negative edge cycle example

All-pairs shortest paths using Johnson’s algorithmThe above example graph contains a negative cycle in it. The negative  cycle is (2>3>4>2) because total sum of edge weight  becomes negative (-2 + 3 -3 ) = -2 . As in above graph the distance from (vertex 0) to (vertex 2) is 3 but if we go through the cycle (2>3>4>2) once , the total cost to reach from (vertex 0) to (vertex 2) will reduce to ( 3 -2 ) = 1. if we go through the cycle in second time the total cost to reach from (vertex 0) to (vertex 2) will become (1 – 2) = -1, which is less than the previous cost. if we continue to go through the cycle again and again then after each iteration cost to travel from (vertex 0) to (vertex 2) will reduced. In this case it is impossible to reach from (vertex 0) to (vertex 3).

All-pairs shortest paths using Johnson’s algorithm

All-pairs shortest paths using Johnson’s algorithm

Johnson’s algorithm does re-weight all edges and make them all positive weighted edge, then apply Dijkstra’s algorithm for every vertex. For removing negative weight Johnson’s algorithm uses Bellman Ford algorithm on original input graph.



Related Contents to follow