in reply to Re^3: Travelling Salesman

in thread Travelling Salesman

I didn't do the analysis and I am guess but it should look something like this. On the whole graph, compute the shortest distance between two points in the graph(From the start point). Then the next shortest distance point from that and so on. Such that already visited points are removed from the graph every time a shortest distance point from the current point is computed.

Every time you find the shortest distance between two points, and reach the destination point. The source point is removed. At each step you end up having a smaller graph. There fore lesser points to work on each step. While at the same time you compute shortest distance point available from the current point.