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.

john_1

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.

john_2

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.

john_3

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.

Implementation

Pre-conditions:

  1. Given graph G.

Algorithm:

  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: https://github.com/alexvolov/algorithms-and-data-structures/blob/master/src/main/java/com/alexvolov/ads/algorithms/graph/JohnsonsAlgorithm.java

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

Leave a Reply