Hamiltonian Path vs Shortest Path
algorithm, complexity-theory
Solution
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.
Problem
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?