1
$\begingroup$

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)

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

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – David Richerby Aug 22 '17 at 17:46
  • $\begingroup$ It seems that Euclidean planar graphs problems are more difficult to resolve than unweighted but I can´t find a proof of that. $\endgroup$ – Ixer Aug 22 '17 at 19:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.