Johnson's Algorithm

[Abhinavcode13]

Describe the solution you'd like

Here is the step-by-step solution approach of Johnson's algorithm:

Add an extra vertex, called the "source vertex," to the given graph. Connect the source vertex to all other vertices with zero-weight edges.

Run the Bellman-Ford algorithm starting from the source vertex to find the shortest path distances from the source to all other vertices. If a negative-weight cycle is detected during this step, the algorithm terminates as the problem is infeasible.

Re-assign the edge weights of the original graph by using the computed shortest path distances. The new weight of an edge (u, v) is calculated as the sum of the old weight of (u, v) and the shortest path distance from the source to u minus the shortest path distance from the source to v.

Remove the extra source vertex added in step 1 and restore the original edge weights.

For each vertex in the graph, run Dijkstra's algorithm starting from that vertex to find the shortest path distances to all other vertices.

Finally, the shortest path distances between all pairs of vertices can be obtained by combining the distances computed in step 2 and step 5.

It's important to note that 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. The Bellman-Ford algorithm is used to compute the shortest path distances in step 2, and Dijkstra's algorithm is used in step 5.

By using Johnson's algorithm, you can efficiently find the shortest paths between all pairs of vertices, even in graphs with negative edge weights, making it a useful tool in various applications, such as network routing and graph analysis.

[Abhinavcode13]

Please assign me this @Kumar-laxmi !!

[Kumar-laxmi]

refer #758