Suponha que um caixeiro viajante precise visitar cinco cidades diferentes (A, B, C, D e E) em uma viagem de negócios. Ele quer encontrar a rota mais curta que o levará a cada cidade uma vez e, em seguida, retornará à cidade de origem. As distâncias entre as cidades são as seguintes:

• A para B: 10 km
• A para C: 15 km
• A para D: 20 km
• A para E: 25 km
• B para C: 35 km
• B para D: 30 km
• B para E: 40 km
• C para D: 45 km
• C para E: 50 km
• D para E: 55 km

Qual é a rota mais curta que o caixeiro viajante deve seguir para minimizar a distância total percorrida?