 # traveling salesman

(classic problem)

Definition: Find a path through a weighted graph that starts and ends at the same vertex, includes every other vertex exactly once, and minimizes the total cost of edges.

Also known as TSP.

Note: Less formally, find a path for a salesman to visit every listed city at the lowest total cost.

The above described path is always a Hamiltonian cycle, or tour, however a Hamiltonian cycle need not be optimal. The problem is an optimization problem, that is, to find the shortest tour. The corresponding decision problem asks if there is a tour with a cost less than some given amount. See [CLR90, page 969].

If the triangle inequality does not hold, that is dik > dij + djk for some i, j, k, there is no possible polynomial time algorithm that guarantees near-optimal result (unless P=NP).

If the triangle inequality holds, you can quickly get a near-optimal solution by finding the minimum spanning tree. Convert the tree to a path by traversing the tree, say by depth-first search, but go directly to the next unvisited node, rather than repeating nodes. Christofides algorithm starts with a minimum spanning tree, but is more careful about converting the tree to a path with results closer to optimal.

Author: PEB

## Implementation

(C, Fortran, Pascal, Mathematica, and C++). Animation and implementation (Icon).