In the traveling-salesman problem we are given a complete graph G = (V, E) that has a cost c(u, v) associated with each edge (u, v) that belongs to E, which is the set of all edges in G. Given this information, we must find a Hamiltonian cycle (a tour) of G with minimum cost.
The instance of the TSP that we are dealing with in this animation is the Euclidean TSP. Thus, the vertices of the graph G are points in the xy-plane, and the cost of traveling between two vertices is the Euclidean distance between them.
For more information on the TSP, please refer to this Comprehensive Survey written as a project for CSE4080.
For more information on recent Polynomial Time Approximation Schemes (PTAS) for the Euclidean TSP, please refer to this PTAS Algorithms Report, also written as a project for CSE4080.
If you can not open this applet with Internet Explorer, use Netscape 6 or higher, or use Mozilla.