Shortest Path :: Optimization for Negative Weighted Edges : Johnson's Algorithm(Subroutine)

[Abhijit2505]

The problem is to find the shortest paths between every pair of vertices in a given weighted directed Graph and weights may be negative. We have discussed Floyd Warshall Algorithm for this problem. The time complexity of the Floyd Warshall Algorithm is Θ(V^3). Using Johnson’s algorithm, we can find all pair shortest paths in O(V^2log V + VE) time. Johnson’s algorithm uses both Dijkstra and Bellman-Ford as subroutines.

Acceptance Condition

• Code is written with proper mentions of edge cases
• Well commented code
• Well documentation(refer to codebase)