Strictly speaking, NP problems need to have boolean outcome, so "what's the shortest path" is not an NP problem. Instead, "is there a path with cost <= X?" is

Strictly speaking, NP problems need to have boolean outcome, so "what's the shortest path" is not an NP problem. Instead, "is there a path with cost <= X?" is an NP problem. Of course, if I had a polynomial-time solver for the "cost <= X?" query, I could easily create a polynomial time solver for the cost of the shortest path, using binary search. See Decision Problem: https://en.wikipedia.org/wiki/Decision_problem https://en.wikipedia.org/wiki/Decision_problem