-2

here is my question. If some edge weights are negative, the shortest paths from s can be obtained by adding a constant C to every edge weight, large enough to make all edge weights nonnegative, and running Dijkstra’s algorithm.

it's true or false and why?

Guan Nan Yao
  • 151
  • 1
  • 1
  • 9
  • 1
    Do **you** think it's true or false and why? (Questions ["must demonstrate a minimal understanding of the problem being solved. Include attempted solutions, why they didn't work, and the expected results."](http://stackoverflow.com/help/on-topic)) – Bernhard Barker Oct 11 '13 at 11:44
  • 2
    Did you read [this](http://stackoverflow.com/questions/6799172/negative-weights-using-dijkstras-algorithm)? – Mauren Oct 11 '13 at 11:45
  • Depends on what meaning negative weights have on your program. You should reconsider using negative weights, and maybe use some other way to do whatever it is you are doing. – Ermir Oct 11 '13 at 11:45

2 Answers2

1

False : If some edge weights are negative, there might be no shortest path.

It would possible to loop into a negative-cost cycle to lower the cost as much as you want.

That's said, if you forbid to use twice the same point, I think that it becomes true.

Even if you forbid using twice the same point, it still does not work as stated by MrSmith42 :

You might have two paths one with costs 0+0+0+0+0+0+0+0+0+0=0 and one with 10+(-4)=6. If you increase all weights by 4, the cost will be 4+4+4+4+4+4+4+4+4+4+4=40 and the other 14+0=10. This way the cheaper path becomes the more expensive ones by changing the weights.

Arnaud Denoyelle
  • 29,980
  • 16
  • 92
  • 148
  • 1
    `"I think that it becomes true"` - no, it doesn't. Consider the graph presented [here](http://stackoverflow.com/a/6799344/1711796). – Bernhard Barker Oct 11 '13 at 11:46
  • Why? In this case, the number of possible paths becomes finite. – Arnaud Denoyelle Oct 11 '13 at 11:47
  • 1
    You might have two paths one with costs 0+0+0+0+0+0+0+0+0+0=0 and one with 10+(-4)=6. If you increase all weights by 4, the cost will be 4+4+4+4+4+4+4+4+4+4+4=40 and the other 14+0=10. This way the cheaper path becomes the more expensive ones by changing the weights. – MrSmith42 Oct 11 '13 at 11:47
0

You are changing the problem to effectively add a penalty of C * the length of the path.

This means that you will potentially get a different answer depending on the value of C.

The larger C becomes, the more your algorithm will bias towards selecting the path from source to destination with the fewest number of edges.

Having said that, if your graph is such that every path from source to destination always has the same length then this approach will work.

Example of a graph for which this would work

enter image description here

Peter de Rivaz
  • 33,126
  • 4
  • 46
  • 75