# Why can't we find shortest paths with negative weights by just adding a constant so that all weights are positive?

I'm currently reading introduction to algorithms and came by Johnson’s algorithm that depends on making sure that all paths are positive.

the algo depends on finding a new weight function (w') that is positive for all edges and keeps the correctness of the shortest paths relations.

It does so by calculating h(s), h(d) values to be added to the w original value.

My question is, why not just find the smallest w in the graph and add it to all edges ? this will satisfy both conditions and will require less calculation.

• Have you tried proving your claim or finding a counter-example? Hint: your intuition is wrong. (Community, I'm pretty sure this is a duplicate. Can you find it?) Commented Jan 20, 2016 at 19:19
• @Raphael I'm pretty sure it's a dupe, too, but I figured it'd be faster to answer it than find the dupe. Commented Jan 20, 2016 at 21:30
• @Raphael I'm sorry since I couldn't phrase my question in a specific format I couldn't search for it. Commented Jan 20, 2016 at 22:33
• We do have a question that already explains this, but it got marked as a dup of another question that is pretty confusing and hard to understand, and that mixes multiple different questions together. Therefore, I think this question has value over what we had before. If you wanted, I suppose we could re-target the dups (close them as a dup of this instead off what they currently point to).
– D.W.
Commented Jan 21, 2016 at 11:20

For example, suppose the lowest-cost edge has weight $$-2$$ and there are two paths from $$a$$ to $$b$$: a single edge of weight $$3$$ and a path with two edges, each of weight $$1$$. The two-edge path has the lowest weight. However, if you add $$2$$ to every edge, the one-edge path has weight $$5$$ but the two-edge path now has weight $$6$$, so you get the wrong answer.