Before analysing an algorithm we have to fix what counts as a valid input, what the output should be, and precisely when an output is correct. Until then, “find the shortest path” is a wish, not a problem.

The correctness relation

Let II be the set of inputs and OO the set of outputs. A computational problem is a relation R⊆I×OR \subseteq I \times O: the pair (x,y)(x, y) belongs to RR exactly when yy is an acceptable answer for xx. Stating it as a relation keeps the door open for inputs that admit several correct answers.

An algorithm AA solves the problem when, for every x∈Ix \in I, it halts and R(x,A(x))R(x, A(x)) holds. Termination and correctness are separate obligations — neither implies the other.