Will all TSP algorithms give the same optimum route?

Question

I was just wondering if all algorithms for the TSP will give the same optimum routes? I thought that this would be the case but ive implemented branch and bound and A* and they both give very different results to the same input, I was just wondering if this is normal?

Answer 1

The route my differ, but the cost of all optimal solution should be the same.

If your A* solution is more expensive, than your heuristic is wrong. Have a look at wikipedia A* algorithm for proofs that it always finds an optimal solution.

Answer 2

No. Provided more than one optimal route exists, different algorithms will not necesarily find the same path. It will depend on the implementation, and I assume it will also depend on how you label the graph, so that different labelings will make the same algorithm find different routes.