Johnson algorithm

Johnson’s algorithm calculates the shortest paths for any pair of vertices in the graph. It has a good complexity for sparse graphs (few edges compared to the number of vertices).

It uses the Dijkstra and Bellman-Ford algorithms, and returns either the matrix of the weights of the shortest paths, or the assertion that the graph has a negative weight circuit.
The idea is to find a graph with only positive weights, then run the Dijkstra algorithm from each vertex. If the weights are not all positive, we redefine them to be able to be reduced to the first case.

The algorithm consists of the following steps:

  1. Add a new node q to the graph, and connect this node with arcs of zero weight to all other nodes.
  2. Use the Bellman-Ford algorithm starting from the new node q to determine, for each vertex v, the minimum weight h(v) of a path from q to v. If a negative cycle is detected, the algorithm stops on a failure.
  3. Reweight the arcs of the initial graph using the values calculated by the Bellman-Ford algorithm: an arc of u to v, whose former weight or length is the number w(u,v), has the new length the number non-negative w(u,v) + h(u) – h(v).
  4. Remove the vertex q and use the Dijkstra algorithm to determine the shortest paths.