I have slight modification for graphs which has negative weights for finding shortest path . If the graph has all non negative weights then by Dijkstra's algorithm , it can be done in O(VlogV + E) . So for the graphs having negative edge weights , find min(weights) = K and subtract K from all weights so that we end up with positive weights. Then apply Dijkstra's instead of bellman ford algorithm which takes O(VE) time to find path and then add K to all paths. Does this method work? If it does then why bellman ford algo is still relevant , If not why?
|Post Closed as "duplicate" by David Richerby, Luke Mathieson, Evil, D.W.♦ of|
Converting Dijkstra for negative weights by adding a O(VE) solution to O(VlogV + E) solution?constant
Converting a O(VE) solution to O(VlogV + E) solution?