Implementation of any Hamiltonian Path Problem algorithm
- by Julien
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
