# Using the decision problem, PATH in order to solve the optimization problem, SHORTEST-PATH in polynomial time

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.

• "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? May 21, 2019 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.