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 com mais de 2 vértices pode ser decomposto em dois menores caminhos:
e
, onde
é um vértice intermediário no caminho
.
Vamos definir como a menor distância do vértice
para o vértice
considerando que o caminho
possui apenas vértices intermediários com índice menor ou igual a
. Assim, para cada par
de vértices, teremos que
=
onde é o peso da aresta
. Se
, então
, e se não existe uma aresta ligando
e
, então definiremos
como
. Perceba que
será exatamente igual ao menor caminho de
para
, 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 - podemos guardar apenas
representando a menor distância atual de
para
, já que quando utilizamos o vértice
como intermediário,
é exatamente igual a
.
Complexidade do algoritmo
A complexidade do algoritmo de Floyd-Warshall é extremamente simples de se calcular. Para cada vértice intermediário de 1 a
, atualizaremos a distância de cada par de vértices
. Logo, a complexidade do algoritmo é
.
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.