Traveling Salesman Problem

From ProofWiki
(Redirected from Travelling Salesman Problem)
Jump to navigation Jump to search


Given any complete (or near-complete) weighted graph, find a minimum-weight Hamilton cycle.


Every complete graph of order $3$ or greater is Hamiltonian.

In this context, near-complete is taken to mean a graph in which the condition for Ore's Theorem is fulfilled, and to spare.

So the problem is not to just find a Hamilton cycle (for large graphs there will be plenty) but to find the best Hamilton cycle.

It is clear that, for a finite graph, there will be a finite number of Hamilton cycles to check.

However, as the number of vertices increases, then the number of Hamilton cycles increases exponentially (in fact, factorially). (See Number of Hamilton Cycles in Complete Graph). Therefore, checking every path and comparing their weights by exhaustion is, indeed, exhausting.

There is no known efficient algorithm that can be guaranteed to produce the minimum-weight Hamilton cycle required.

There are known to be some relatively efficient approximate solutions, some of which work pretty well.

The Traveling Salesman Problem is NP-Complete. This makes finding an efficient algorithm for the solution unlikely.


The problem gets its name from the practical application of a salesman, traveling to a number of cities, looking for the optimum route that will keep the distance travelled to a minimum. It is understood that the distance between each pair of cities is known (thereby establishing that the game plan is a complete weighted graph).

Linguistic Note

The UK English spelling of the Traveling Salesman Problem is Travelling Salesman Problem.