0

Suppose there are two points $s$ and $t$, and that edges can have negative length and that

from each vertex there is at least one directed path to $t$,

how do I show that the statements "there is no circuit with negative total length" and "there is a shortest $s-t$ path" are equivalent?

I asked a different version of this here:
Equivalence of following statements about shortest path problem
so if you post the answer there, I can give you a bounty.
Please note, that this question differs from the one linked because of the crucial extra assumption included above.

Community
  • 1
  • Imagine if you had a circuit with negative total length. Now assume you have a shortest path between $s$ and $t$. Now travel along that shortest path and then take the circuit with negative total length, which will give you a new path that is even shorter than the shortest path. That is a contradiction, so there cannot be a shortest path if there exists a circuit with negative total length. I'm not sure how to prove the converse, though. – eyqs Oct 25 '15 at 17:56
  • Actually, I do know how. Imagine if there were no shortest path. Now consider any path. Since there is no shortest path, there must be a path that is shorter than that path. The only way for there to exist paths that are always shorter than any given path is if there is some circuit with negative total length. – eyqs Oct 25 '15 at 17:58
  • @eyqs If you could make that a full answer and post it at http://math.stackexchange.com/questions/1486017/equivalence-of-following-statements-about-shortest-path-problem, I can give you a bounty –  Oct 25 '15 at 18:15
  • I would, but @5xum provides a convincing counterexample when you don't include the extra condition that each vertex has at least one directed path to $t$. I'll post my comments as an answer to this question and upvote your bountied question, as I'd like to see the proof of (i) and (ii) myself. – eyqs Oct 25 '15 at 18:17

1 Answers1

0

You have to actually add another restriction for them to be equivalent: that you can actually reach the circuit with negative total length from $s$. If you can't reach the circuit from $s$, then you can't go around the circuit! But if you can reach the circuit, then...

Imagine if you had a circuit with negative total length. Assume you have a shortest path between $s$ and $t$. Instead of taking that path, travel along a new path that is connected to the circuit with negative total length, and keep going around the circuit until the total length of the new path is less than the length of the shortest path. You know that this path that contains the negative circuit is a valid path because all vertices have at least one path that leads to $t$, so any vertex on the circuit can eventually get to $t$.

But that is a contradiction, since the shortest path is not the shortest anymore, which means that if there exists a circuit with negative total length, there cannot be a shortest path.

Now imagine if there were no shortest path. Consider any path. Since there is no shortest path, there must be a path that is shorter than that path. The only way for there to exist paths that are always shorter than any given path is if there is some circuit with negative total length; otherwise, there is only one possible total length when you go through a straight path, and if you keep on going around a circuit with positive total length, the length of your path can only increase. That proves both directions of the equivalency, and so the two statements are equivalent.

eyqs
  • 521