CODEWITHSUNDEEP
algorithmcomplexity-theory
cgval
cgval

Reputation: 1096

Hamiltonian Path vs Shortest Path

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?

Upvotes: 4

Views: 16204

Answers (2)

smilingfish
smilingfish

Reputation: 7

The difference between the longest path and the shortest path between any nodes is that the shortest path problem has an optimal substructure, and thus it can be solved with dynamic programming; the longest path problem doesn't have an optimal substructure, and it cannot be solved using dynamic programming. A problem is said to have optimal substructure if an optimal solution can be constructed from optimal solutions of its sub-problems. example

an example would be as the above graph. the shortest path from q to t include the shortest path from q to r. However, the longest path from q to t is q-r-t, the longest path from q to r is q-s-t-r, which is not included in the q-r-t. That's because the sub-problems of the longest path is not independent from each other. the longest path from q to r is q-s-r-t. The longest path from r to t is r-q-s-t. These two problem have over-lapping, so they are not independent, so this problem doesn't have optimal-substructure, so that it can not be solved by dynamic programming nor greedy algorithm.

Upvotes: 0

amit
amit

Reputation: 178451

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.

Upvotes: 11

Related Questions