Implementation of any Hamiltonian Path Problem algorithm

Question

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

Edit : the problem is that I have to recreate a list of geographic points which represent bus stops, and I have to figure out a realistic sequence. Performance is not important at all since the goal is only to populate a database.

Edit : Here is a picture :

Answer 1

The Bellman-Ford algorithm is often used to solve single-source shortest path problems.

The shortest Hamiltonian Path problem belongs to a class of problems known as NP-hard. This means that you have to try all of the permutations to guarantee to find the shortest path. This approach is only practical for small problems, within a normal human life span.

You can use the Bellman-Ford algorithm to produce a set of single source shortest paths for each node to help you to solve the problem, but you might find the Floyd-Warshall algorithm preferable. Floyd-Warshall will give you the shortest path from every node in the graph to each of the other nodes. It's an O(N^3) algorithm with O(N^2) memory requirements.

Once you have the shortest paths between the nodes then you can either try all of the permutations to find the shortest Hamilton Path, or you can use a heuristic algorithm to start from a basic feasible solution and iterate to an approximation of the shortest path.

I've had some success with Simulated Annealing and Tabu Search. There was also a rather interesting approach based on ant trails that was published around the last time I had to solve this type of problem.

Good luck.

Answer 2

The Hamiltonian path problem is NP-complete, so obviously you can't find a solution using the Bellman-Ford algorithm, which is polynomial.

You can use the following steps to solve the Hamiltonian Path Problem:

• First transform the Hamiltonian Path Problem into the Hamiltonian Cycle Problem. To achieve this, add a vertex to your initial graph and connect it to all existing vertices.

• Then transform the Hamiltonian Cycle Problem into the Travelling Salesman Problem, by creating a complete graph and assigning weight = 0 to the edges present in the previous graph and weight = 1 to the rest of the edges.

• Finally, solve the TSP by using a known algorithm (e.g. dynamic programming).

Edit: I just realised that you seek the shortest path. With the above you can only answer if a graph does have a Hamiltonian path (and probably find one).

Answer 3

This is called Euclidean Travelling Salesman (in 2-dimensions) and is also NP-Complete like TSP.

The other answers are inaccurate as they are doing the opposite: reducing your problem to Hamiltonian Path, while it should be the other way round, to show NP-Completeness. Sorry to say this, but it seems to be a pretty common problem on this site.

We can say that this fundamentally differs from the normal TSP in the following sense:

If P != NP,

• There is no PTAS for TSP (in fact also for metric TSP, where distances satisfy the triangle inequality).

• There is a PTAS for Euclidean TSP. Check out this paper by Arora by which gives an 1+1/c approximation algorithm and runtime is O(n (logn)^O(c)): Polynomial time approximation schemes for Euclidean TSP and other geometric problems. Notice that Euclidean TSP is a special case of metric TSP and yet it differs in this way.

There are other algorithms which guarantee 2-approximation (using Minimum Spanning Trees) and 3/2-approximation and might be simpler. Arora's paper mentions those and you should be able to track down using the references in Arora's paper.