1
$\begingroup$

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?

$\endgroup$

marked as duplicate by David Richerby, Luke Mathieson, Evil, D.W. algorithms Feb 1 '18 at 17:09

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1
$\begingroup$

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.)

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.