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.
- Given graph G.
- Create a new vertex s.
- Connect vertex s with all vertices.
- Calculate distance D starting from s using Bellman-Ford algorithm. If negative weight cycle is detected terminate the algorithm.
- For each edge from u to v change weight w(u, v) by formula: w(u,v) + D(u) − D(v).
- Remove s from G.
- Run Dijkstra’s algorithm for each node to get shortest path to other nodes.
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).