Johnson's algorithm | Toward MOON

25.3 Johnson's algorithm for sparse graphs

  Johnson's algorithm finds shortest paths between all pairs by using both Dijkstra's algorithm and the Bellman-Ford algorithm.

  Dijkstra's algorithm and the Bellman-Ford algorithm finds shortest paths from the single source vertex to others. Dijkstra's algorithm runs in O(n*lg n) to compute shortest paths while the Bellman-Ford runs in O(n*m), where n is the number of vertices and m is the number of edges. Thus, Dijkstra's algorithm is strictly faster than the Bellman-Ford for both sparse and dense graphs. However, Dijkstra's algorithm has one shortcoming, which is the constraint that the input graph must not have negative cost edges. On the other hand, the Bellman-Ford allows the input graph to have negative cost edges, but no negative cost cycles.

  To overcome the constraints of the two single source shortest path algorithms, Johnson's algorithm uses the technique of re-weighting. Johnson's algorithm follows the steps below.

  Given a weighted, directed graph G=(V,E) with weight function w : E -> R. Weights might or might not be negative.

1. Form G' by adding a new vertex s and a new edge (s,v) with weight 0 for each v in V.
2. Run Bellman-Ford algorithm on G' with source vertex s
   (If B-F algorithm detects a negative cost cycle in G', halt and report this).
3. For each v in G, let P[v] be the length of a shortest path from s to v in G'. For each edge e = (u,v) in G, define 'new weight' = 'old weight' + P[u] - P[v].
4. For each vertex u of G:
     Run Dijkstra's algorithm in G with edge costs {new weights}, with source vertex u to compute the shortest path distance d'(u,v) for each v in G.
5. For each pair (u,v) in G, return the shortest path distance d(u,v) = d'(u,v) - P[u] + P[v].

Read full article from Johnson's algorithm | Toward MOON