The author uses NP-complete correctly. Section 2.2 of the paper establishes the problem is in NP and not merely NP-hard.

Your intuition about verifying optimal solutions has misled you here. Interesting optimization questions such as "shortest" or "best" are conventionally reformulated as decision questions about a particular bound. The verification then becomes easy: check to see, for instance, that the certificate path works and is shorter than the specified bound. A log-time search with such a verifier as a subroutine produces a polynomial verifier for the original optimality question.