Johnson’s algorithm solves** the all-pairs shortest path problem** on a graph which may contain negative weight but has no negative weight cycle. In other words, it searches for the shortest distance between every pair of vertices in a given directed graph. The algorithm uses Bellman-Ford algorithm to prepare graph for re-weighting.

The re-weighting technique changes all negative weights to nonnegative. Thus, once we get rid of all negative weights we can use Dijkstra’s algorithm that is faster than Bellman-Ford algorithm to obtain shortest path between all pair of vertices.

Before, we run Bellman-Ford algorithm we need to add a new vertex and connect it to all others with zero weight.

As result we have a vertex from which every node can be accessed and now it is time run Bellman-Ford algorithm from this new node. Continue reading Johnson’s Algorithm