Aula por Lúcio Cardoso
Algoritmo de Floyd-Warshall
O algoritmo de Floyd-Warshall é utilizado para calcular a menor distância entre todos os pares de vértices do grafo, diferentemente do algoritmo de Dijkstra. A ideia do algoritmo consiste em perceber que todo menor caminho $$u \to v$$ com mais de 2 vértices pode ser decomposto em dois menores caminhos: $$u \to k$$ e $$k \to v$$, onde $$k$$ é um vértice intermediário no caminho $$u \to v$$.
Vamos definir $$d(u, v, k)$$ como a menor distância do vértice $$u$$ para o vértice $$v$$ considerando que o caminho $$u \to v$$ possui apenas vértices intermediários com índice menor ou igual a $$k$$. Assim, para cada par $$(u, v)$$ de vértices, teremos que
$$d(u, v, k)$$ = $$\begin{cases} w(u, v) & , \mbox{se k = 0} \\ min \big (d(u, v, k-1), d(u, k, k-1) + d(k, v, k-1) \big ) & , \mbox{caso contrario}\end{cases}$$
onde $$w(u, v)$$ é o peso da aresta $$(u \to v)$$. Se $$u = v$$, então $$d(u, v, 0) = 0$$, e se não existe uma aresta ligando $$u$$ e $$v$$, então definiremos $$d(u, v, 0)$$ como $$\infty$$. Perceba que $$d(u, v, N)$$ será exatamente igual ao menor caminho de $$u$$ para $$v$$, já que poderemos usar qualquer vértice como vértice intermediário.
A implementação do algoritmo de Floyd-Warshall é bastante simples. Confira o código abaixo:
Perceba que durante o código, não é necessário guardar $$d(u, v, k)$$ – podemos guardar apenas $$d(u, v)$$ representando a menor distância atual de $$u$$ para $$v$$, já que quando utilizamos o vértice $$k$$ como intermediário, $$d(u, v)$$ é exatamente igual a $$d(u, v, k)$$.
Complexidade do algoritmo
A complexidade do algoritmo de Floyd-Warshall é extremamente simples de se calcular. Para cada vértice intermediário $$k$$ de 1 a $$N$$, atualizaremos a distância de cada par de vértices $$(u,v)$$. Logo, a complexidade do algoritmo é $$O(N \cdot N^2) = O(N^3)$$.
Observação
O algoritmo apresentado acima funciona em grafos com arestas de pesos não-negativos e não funciona caso alguma delas tenha peso negativo.