# Shortest Hamiltonian Path in a Complete Graph

I know that, in general, the Shortest Hamiltonian Path Problem in a general weighted graph is NP-complete. I am wondering, however, if the restriction to a complete weighted graph admits an algorithm in P. Being in a complete graph does give the knowledge that a Hamiltonian path exists in the first place.

My guess is that if such an algorithm exists, it will be some modification of a DFS or potentially modifying a minimal spanning tree in some way to arrive at the solution.

• What is a "shortest Hamiltonian path"? By definition, all Hamiltionian paths have same length… Dec 2, 2023 at 20:17
• Do you mean Travelling Salesman Problem? Dec 2, 2023 at 20:23
• No, the shortest Hamiltonian path problem is finding the Hamiltonian path starting at a given vertex in a weighted graph that minimizes the edge weights, it is not Travelling Salesman and not all Hamiltonian paths have the same length in a weighted graph. (Kind of like the shortest path problem in a weighted graph). It is similar to Travelling Salesman though but instead of looking for a Hamiltonian cycle, the problem looks for a Hamiltonian path (i.e. there is no restriction that the path must terminate where it began). Dec 2, 2023 at 20:31
Here is the reduction. Suppose you have an arbitrary graph $$G$$, with no edge weights/lengths, and we want to know whether it has a Hamiltonian path or not. Treat every edge of $$G$$ as having length 1. Then, add all missing edges, but with edge length of some huge number (larger than $$|V|$$, the number of vertices in $$G$$), so now you have a complete graph. Suppose you had an efficient way to find the shortest Hamiltonian path in any complete graph. Then you could find the shortest Hamiltonian path in this complete graph. If its total length is less than $$|V|$$, then it is a Hamiltonian path for $$G$$ (it obviously can't include any of the huge-length edges); if its total length is $$\ge |V|$$, then $$G$$ has no Hamiltonian path.