///
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 ao lado 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:
| Cidades | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 1 | 0 | 2 | 1 | 2 | ∞ | 5 |
| 2 | 2 | 0 | 3 | ∞ | ∞ | ∞ |
| 3 | 1 | 3 | 0 | 2 | 10 | ∞ |
| 4 | 2 | ∞ | 2 | 0 | 5 | 1 |
| 5 | ∞ | ∞ | 10 | 5 | 0 | 4 |
| 6 | 5 | ∞ | ∞ | 1 | 4 | 0 |