Skip to main content
Computer Science

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

Required fields*

4
  • $\begingroup$ Thank you for your answer! Yet, by saying : construct an instance $I'$ of SPP such that $I$ has a solution if and only if $I'$ has a solution. So giving a weight of -1 and calculate the shortest path from i→j. and testing IF the path length is -(n-1) gives such an $I'$, isn't it? The thing I don't understand is why the condition test if it has a solution, does it mean that we got through another vertices before concluding? Last, I don't understand your last sentence. $\endgroup$ Commented Nov 12, 2016 at 23:12
  • $\begingroup$ @Marine1 Yes, so in other words, the instance of $I'$ will consists of exactly same graph it is in $I$, and you set the weight of every edge to -1. Now there are two directions to prove: (1) if $I$ has a solution, then $I'$ has a solution, and (2) if $I'$ has a solution, then $I$ has a solution. If I were you, I would insist on having a reduction that uses the definition that has been given to you (many-one reduction, like you describe in your comment to your question). Basically, you don't need to know about oracle reductions at this point. $\endgroup$ Commented Nov 13, 2016 at 9:09
  • $\begingroup$ Isn't this only true for shortest simple paths? Shortest path problem can be solved using classic algorithms if there are no negative cycles. $\endgroup$ Commented Apr 4, 2021 at 20:48
  • $\begingroup$ @Ari This answer is about simple paths, yes. $\endgroup$ Commented Apr 4, 2021 at 21:19