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?
$\begingroup$
$\endgroup$
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
0
No, this doesn't work. A path of length $\ell$ will have $\ell K$ added to its weight, so your transformation can make a path with several light edges weigh more than a path with a few medium-weight edges. (Consider the effect of adding $2$ to each weight in a path of two weight-$1$ edges vs a path of a single weight-$3$ edge.)
answered Feb 1, 2018 at 0:42