Re^5: Travelling Salesman

[JavaFan]

That sounds like you're computing the smallest spanning tree. Which is *not* what Dijkstra's algorithm is doing. Given a smallest spanning tree, one can compute an approximation of the shortest hamiltonian path, which I think is at most a factor 2 off.

Dijkstra's algorithm in a nutshell:

1. Mark all nodes in the graph unvisited with distance infinite.
2. Mark the start node unvisited with distance 0.
3. Off all the unvisited nodes, pick the one (or one of) with smallest distance. Call this node X.
4. For all unvisited neighbours of X, calculate their distance to the start node (which is the distance X has, plus the length of the edge between X and its neighbour). If said distance is less than the current distance stored at the neighbour, update the distance.
5. Mark X as visited. If X is the destination node, you're done.
6. Goto 3. (Hah! A Goto in Dijkstra's algorithm. The irony...)