So, if I were using a black-box decision algorithm, PATH in which I could say, "does a path of weight k exist in this graph from S to V", problably the typical way one would solve the optimization problem of shortest path is to start at k at zero and increment until PATH returns true. But since paths start at -inf shouldn't we be starting there? (Thus making this optimization problem not solvable in polynomial time)

I know this isn't right, I'm just having a hard time seeing which part I am missing here.

  • $\begingroup$ "Since paths start at -inf shouldn't we be starting there?" Why should we start at -inf? Can you explain why we shouldn't start at 100000000 or even +inf? $\endgroup$ – John L. May 21 '19 at 3:06

For non-negative weights $0$ is a lower bound and thus sufficient. For arbitrary weights you can binary search in $[l,u]$, for a lower bound $l=\sum_{a\in A\mid d_a<0} d_a$ and an upper bound $u=\sum_{a\in A\mid d_a>0} d_a$ on the length of any simple path.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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