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.