# Is there an algorithm to compute the shortest Hamiltonian path in an directed graph from one point to another in polynomial time?

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.

• It is easy to reduce this problem to not-returning-to-starting-city variant of travelling salesman problem, or to Hamiltonian path problem. Commented Mar 8, 2018 at 11:30
• 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? Commented Mar 8, 2018 at 15:33
• @j_random_hacker The edges have weights, so I think the smallest total weight of the edges in the path is meant. Commented Mar 8, 2018 at 17:38
• @Discretelizard: Thanks, I completely missed that! Commented Mar 8, 2018 at 17:41

## 1 Answer

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.

• 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/… Commented Mar 9, 2018 at 1:28