The travelling salesman problem is a problem that asks “Given a set of cities, and the distances between each pair of cities, what is the shortest possible route that visits every city once and returns to the starting city?”. In terms of graphs, the travelling salesman asks for a hamiltonian cycle of a complete weighted graph with the lowest possible weight. The nodes represent the cities, and the edge weights the distance between cities
The travelling salesman problem is NP-Complete, and so currently there are no known polynomial-time solutions to the problem.