I am wondering whether the Shortest Hamiltonian Path (SHP) problem is NP-Complete, because I couldn't find a way of solving it in a polynominal time. if it is NP_Complete, it will be so kind of you to give me the proof or the relevent papers,thanks a lot

the problem explanation: Given a directed,weighted graph with n vertices, find the shortest hamiltonian path with end vertices v and u. by the way,the graph must exit a hamiltonian path from v to u.

  • 1
    $\begingroup$ It is easy to reduce this problem to not-returning-to-starting-city variant of travelling salesman problem, or to Hamiltonian path problem. $\endgroup$
    – xskxzr
    Commented Mar 8, 2018 at 11:30
  • 1
    $\begingroup$ It's not clear what you mean by "the graph must exit a hamiltonian path from v to u". Do you mean that the algorithm must output a path? $\endgroup$
    – Pål GD
    Commented Mar 8, 2018 at 15:33
  • 1
    $\begingroup$ @j_random_hacker The edges have weights, so I think the smallest total weight of the edges in the path is meant. $\endgroup$
    – Discrete lizard
    Commented Mar 8, 2018 at 17:38
  • $\begingroup$ @Discretelizard: Thanks, I completely missed that! $\endgroup$ Commented Mar 8, 2018 at 17:41

1 Answer 1


Here's a small hint.

Let $G$ be a directed graph with unit weights, and $u$ and $v$ be two vertices. Suppose that I could solve SHP in polynomial time, say, $O(n^c)$.

Now, say that I would like to solve Hamiltonian Path on a directed graph. Let me spend $O(n^2)$ time to "guess" your vertices $u$ and $v$, and for each of them run your algorithm for SHP. Then, I would in $O(n^{c+2})$ time have either found a Hamiltonian path in $G$, or conclude that $G$ is not Hamiltonian.

That would mean that P = NP.

Now, this doesn't prove that your problem in NP-complete. For that, you need to come up with a reduction. But it does tell you that you should probably not spend too much time looking for a polynomial time algorithm.

  • $\begingroup$ thanks a lot. After looking at your answer I think that I make a mistake when I abstract this problem, the original problem is at cs.stackexchange.com/questions/89092/… $\endgroup$
    – yingwan
    Commented Mar 9, 2018 at 1:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.