14
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ 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?) $\endgroup$
    – Raphael
    Commented Jan 20, 2016 at 19:19
  • $\begingroup$ @Raphael I'm pretty sure it's a dupe, too, but I figured it'd be faster to answer it than find the dupe. $\endgroup$
    – David Richerby
    Commented Jan 20, 2016 at 21:30
  • $\begingroup$ @Raphael I'm sorry since I couldn't phrase my question in a specific format I couldn't search for it. $\endgroup$
    – Mr.Me
    Commented Jan 20, 2016 at 22:33
  • 1
    $\begingroup$ 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). $\endgroup$
    – D.W. ♦
    Commented Jan 21, 2016 at 11:20

2 Answers 2

Reset to default
25
$\begingroup$

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

Improve this answer
$\endgroup$
0
$\begingroup$

Increasing every edge weight by the same amount does not necessarily increase every path by the same amount of distance. Rather, the increase to the paths are often disproportional which depends on how many edges the path has.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ This effect is already mentioned in the other answer. $\endgroup$
    – Yuval Filmus
    Commented Sep 20, 2017 at 8:47
  • $\begingroup$ I just rephrased it to the point of confusion. $\endgroup$
    – Pendechosen
    Commented Sep 20, 2017 at 14:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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