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.

###### Implementation

*Pre-conditions:*

- Given graph
**G**.

*Algorithm:*

- 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.
- 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).