Floyd-Warshall

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.