Um despachante de longas distâncias é responsável pela rota de caminhões de uma determinada região que contém 6 cidades. Muitas vezes, para sair de uma cidade e chegar a outra, é necessário passar por cidades intermediárias. A matriz de distâncias entre as cidades é dada abaixo com valores em centenas de quilômetros. Quando não existe conexão direta entre as cidades, o custo dado é infinito. A menor distância para o despachante sair da cidade 5 e chegar na cidade 2 é de: