O problema do caixeiro viajante faz referência a um vendedor em uma viagem de negócios. Ele começa em sua cidade natal (A) e depois precisa passar por diversas cidades diferentes para vender seus produtos (as outras cidades são B, C, D, etc.). Para resolver esse problema, você precisa encontrar a maneira mais barata para que o vendedor saia da sua casa, visite outras cidades e depois retorne a sua casa no final da viagem, passando apenas uma vez em cada cidade. A solução do problema exige a determinação do caminho hamiltoniano com o menor custo. O caminho hamiltoniano passa apenas uma vez em cada vértice de um grafo. Suponha que um transportador com sede na localidade A precisa entregar pacotes em quatro localidades B, C, D e E e retornar ao escritório central A, passando apenas uma vez em cada localidade. A figura abaixo mostra a distância em milhas entre as localidades A, B, C, D e E.
O transportador tem um custo por milha de R$5,90. Qual será o valor da rota mais curta que permite que o transportador faça as entregas saindo de A, passando por todas as outras localidades, uma única vez, e retornando a localidade A?