# 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. – Yuval Filmus Jun 25 '14 at 5:41
• It's definitely NP-complete; I'm assuming you'd be looking for a proof of NP-completeness? – Dennis Meng Jun 25 '14 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! – Raphael Jun 25 '14 at 6:28