# 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. – xskxzr Mar 8 '18 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? – Pål GD Mar 8 '18 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. – Discrete lizard Mar 8 '18 at 17:38
• @Discretelizard: Thanks, I completely missed that! – j_random_hacker Mar 8 '18 at 17:41

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.