Problema do Menor Caminho

Problema do Caminho Mínimo

O problema do caminho mínimo consiste basicamente: dado um grafo com pesos nas arestas, obter o caminho de menor custo entre dois vértices x e y. Como muitas vezes o peso representa a distância entre os vértices este problema passou a ser conhecido como problema do caminho mínimo.
Anteriormente avaliamos o algoritmo conhecido como algoritmo de Dijkstra para a resolução deste problema, sendo que ele basicamente consistia em: para chegar do nó x ao nó y construíamos um conjunto que continha inicialmente apenas x, e, ao longo do algoritmo, adicionávamos a ele os nós cujas menores distâncias de x já haviam sido determinadas. Para todo nó fora deste conjunto guardávamos uma distância de x e avaliávamos se esta distância era maior do que do “nó atual” no algoritmo até y, se fosse verdade então podíamos dizer que o menor caminho para se chegar de x a y era vindo pelo “nó atual”.
Neste texto avaliaremos outro algoritmo para se obter o caminho mínimo dentre 2 vértices conhecido como algoritmo de Floyd-Warshall e para entender seu funcionamento vamos supor o seguinte problema:
Como descobrir o caminho de menor custo dentre todos os pares de vértice em um grafo? O problema poderia ser revolvido executando-se o algoritmo de Dijkstra de cada nó para cada nó em um grafo e armazenando-se esses valores em uma tabela, assim, ao final do algoritmo, teríamos a menor distância de um nó qualquer a outro nó qualquer (suponde-se que trata-se de um grafo conexo).
No entanto, outra saída para o mesmo problema seria executar o algoritmo de Floyd-Warshall que consiste apenas de três “for” encadeados alcançando-se um mesmo resultado. Abaixo será explicado seu funcionamento, no entanto, não apresentaremos sua prova formal nem sua análise assintótica.
O Funcionamento
Assim como o algoritmo de Dijkstra o algoritmo de Floyd-Warshall recebe como entrada uma matriz de adjacência representando um grafo conexo e com pesos em suas arestas. O valor do caminho