How to use Johnson’s algorithm for shortest paths?

Johnson's algorithm is used to find the shortest paths between all pairs of vertices in a weighted, directed graph.

To use Johnson's algorithm, first add a new vertex to the graph and connect it to all existing vertices with zero-weight edges. Then, run Bellman-Ford algorithm on the modified graph to find the shortest path from the new vertex to all other vertices. If there is a negative cycle in the graph, the algorithm will detect it.

Next, reweight the edges of the original graph using the distances found by Bellman-Ford. Specifically, for an edge (u, v) with weight w(u, v), the new weight is w(u, v) + h(u) - h(v), where h(u) and h(v) are the distances from the new vertex to u and v, respectively.

Finally, run Dijkstra's algorithm on the reweighted graph for each vertex as the source to find the shortest paths to all other vertices. The shortest path between vertices u and v is the sum of the reweighted edge weights along the path from u to v.

Johnson's algorithm has a time complexity of O(V^2 log V + VE), where V is the number of vertices and E is the number of edges in the graph. It is more efficient than Floyd-Warshall algorithm for sparse graphs with negative edge weights.