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)

Improve this question
$\endgroup$
3
  • 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
    Commented Jun 25, 2014 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
    Commented Jun 25, 2014 at 5:48
  • 4
    $\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
    Commented Jun 25, 2014 at 6:28

1 Answer 1

Reset to default
2
$\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?

Improve this answer
$\endgroup$
2
  • $\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
    Commented Aug 22, 2017 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
    Commented Aug 22, 2017 at 19:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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