Implementation of any Hamiltonian Path Problem algorithm

Posted by Julien on Stack Overflow See other posts from Stack Overflow or by Julien
Published on 2010-05-25T19:01:40Z Indexed on 2010/05/25 19:41 UTC
Read the original article Hit count: 408

Filed under:
|
|

Hi all !

Here is my problem : I have an array of points, the points have three properties : the "x" and "y" coordinates, and a sequence number "n". The "x" and "y" are defined for all the points, the "n" are not. You can access and write them calling points[i]->x, points[i]->y, points[i]->n. i.e. :

points[i]->n = var
var = points[i]->n

So the title maybe ruined the surprise, but I'm looking for a possible implementation of a solution to the Hamiltonian path problem : I need to set the "n" number of each point, so that the sequence is the shortest path (not cycle, the edges have to be disjoint) that goes exactly once through each point. I looked for a solution and I found The Bellman Ford Algorithm but I think it doesn't work since the problem doesn't specify that it has to go through all of the points is it correct ?

If it is, does somebody has another algorithm and the implementation ? If the Bellman Ford Algorithm works, how would I implement it ?

Thanks a lot,

Julien

© Stack Overflow or respective owner

Related posts about algorithm

Related posts about geometry