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

Assumptions:

• given a graph with N nodes, and two specific nodes A and B
• the graph is undirected and no edge has a negative cost
• there exists at least one Hamiltonian path with A and B as an end points

Is there a way to find the shortest path from A to B that passes through all the other points?

Note: I'm only concerned with the specific given nodes A and B as endpoints, thus there's no need to compute for other Hamiltonian paths with different endpoints.

I'm thinking if it's possible to modify Dijkstra's shortest path algorithm to find Hamiltonian paths. Is it possible? If so, how? If not, is there any other algorithm that can be used? (in polynomial time)

• The decision version of the problem is probably NP-complete, so there is probably no such algorithm. You can always introduce a useless Hamiltonian path from A to B by artificially adding one of very high cost. Commented Jun 25, 2014 at 5:41
• It's definitely NP-complete; I'm assuming you'd be looking for a proof of NP-completeness? Commented Jun 25, 2014 at 5:48
• Welcome to Computer Science! Your question is very famously an open one. Let me direct you towards our reference questions which contain more information (cf the complexity theory section). Please work through the related questions listed there. Good luck! Commented Jun 25, 2014 at 6:28

The case you are describing is NP-complete, so the answer is no.

I don't know if still remains NP-complete if the graph is a Euclidean graph. Anyone knows?

• Hamiltonian Path is still NP-complete for unweighted planar graphs (see, e.g., Wikipedia). I doubt Euclidean weights would make much difference (e.g., metric TSP is still NP-hard, for example) but I'm not an expert on Hamiltonian paths. Commented Aug 22, 2017 at 17:46
• It seems that Euclidean planar graphs problems are more difficult to resolve than unweighted but I can´t find a proof of that.
– Ixer
Commented Aug 22, 2017 at 19:17