///
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 | \(\infty\) | 5 |
| 2 | 2 | 0 | 3 | \(\infty\) | \(\infty\) | \(\infty\) |
| 3 | 1 | 3 | 0 | 2 | 10 | \(\infty\) |
| 4 | 2 | \(\infty\) | 2 | 0 | 5 | 1 |
| 5 | \(\infty\) | \(\infty\) | 10 | 5 | 0 | 4 |
| 6 | 5 | \(\infty\) | \(\infty\) | 1 | 4 | 0 |