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.