Is the Bellman-Ford algorithm pseudo-polynomial?

Question

We know that the problem of finding a shortest path that visits each node at most once is NP-hard. It seems to me that Bellman-Ford does that but its time complexity it $O(mn)$ so polynomial. Isn't this contradictory? If so, does that imply that the algorithm is pseudo-polynomial?

Answer 1

First, if Bellman--Ford encounters a negative weight cycle, then the algorithm aborts. So if the input graph does not have a negative weight cycle, the algorithm will correctly compute the shortest paths.

Now note that $m \leq \binom{n}{2}$. So the algorithm is not pseudo-polynomial; rather, Bellman--Ford runs in time $O(n^{3})$. In particular, if the input graph has no negative weight cycle, then the Hamiltonian Path problem is- assuming P and NP are different- not NP-hard on this family of graphs.