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

Question

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.

Answer 1

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.