My problem: Find the shortest path from node A to node B that passes through all other nodes of the unweighted, direct graph. I know that there exists such a path.
I believe this is NP-Hard, but I can't explain it. My Prof. likes to have the algorithm perform on a runtime of O(|V| + |E|), where V is the set of nodes and E the set of edges.
It seems it is similar to this problem, but the Graph's properties are different, does it make a difference?
Yes it's NP-hard. If your solver ran in P, then by running it on every pair of points you'd have a P-time solver for Hamiltonian Path.
The answer you linked gives a more rigorous proof.