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

Problem Detail: 

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.

Asked By : Mr.Me

Answered By : David Richerby

Adding a weight to every edge adds more weight to long paths than short paths. (Long in the sense of having many edges.)

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 three-edge path now has weight $6$, so you get the wrong answer.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/52080