Johnson’s Algorithm

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. The algorithm will evaluate distance from node “4” to others.


In the next step, we are re-weighting the all edges using formula: w(u,v) + h(u)h(v). Where, w is a function that returns weight between vertex u and v.


Finally, we can remove new node “4” and run Dijkstra’s algorithm for all vertices in the graph. The result can be represented as matrix.



  1. Given graph G.


  1. Create a new vertex s.
  2. Connect vertex with all vertices.
  3. Calculate distance D starting from using Bellman-Ford algorithm. If negative weight cycle is detected terminate the algorithm.
  4. For each edge from u to change weight w(u, v) by formula: w(u,v) + D(u) − D(v).
  5. Remove from G.
  6. Run Dijkstra’s algorithm for each node to get shortest path to other nodes.
  7. End.

Here goes my version of the Johnson’s Algorithm on GitHub:

Time complexity of this algorithm is O(V^2 logV+VE).

Leave a Reply