Hamiltonian Path vs Shortest Path

Question

After researching about both problems, I can't conclude what is the difference amongst them.

Hamiltonian Path

A Hamiltonian path is a path between two vertices of a graph that visits each vertex exactly once. Given a graph G and two distinct nodes S and E, is there a Hamiltonian path in G from S to E?

I've found that this problem is NP-Complete

Shortest Path

In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. This problem is P

What is the actual difference between them? And how is their complexity calculated?

Answer 1

The Hamiltonian Path problem is actually looking for a longest simple path in a graph. It is easy to see that the two problems are basically equivalent (longest simple path and hamiltonian path). This problem is indeed a classic NP-Complete Problem.
It is NP-Complete since there is a polynomial reduction from another (already proved) NP-Hard Problem to this problem, and thus (from transitivity of polynomial reductions) this problem is NP-Hard as well. Since it is also in NP, it is NP-Complete.

The shortest path on the other hand is a different one, it asks what is the shortest way from point A to point B, and it is in P because there is a polynomial time algorithm that solves it (Dijkstra's algorithm, Bellman-Ford, BFS for non weighted graphs).

---

Regarding "And how is there complexity calculated?" I assume you mean how do we determine their complexity classes - in this case, Shortest Path is in P because we have a deterministic polynomial time algorithm that solves it (some mentioned above), while the complexity class of Hamiltonian Path is NP-Complete because it is both NP-Hard (there is polynomial reduction from another proven NP-Hard problem), and NP (we can solve it easily in polynomial time on non-determinitic turing machine).
Note that we DO NOT KNOW if Hamiltonian Path is in P or not, because we do not know if P=NP.