O algoritmo de Floyd–Warshall

Os velhos atlas rodoviários tinham uma tabela no fim: a distância entre cada par de cidades. O Floyd–Warshall é uma forma de calcular uma tabela assim, e é um dos algoritmos mais curtos alguma vez escritos: três ciclos, uma comparação, e cada distância mais curta fica no seu lugar.

Um pequeno grafo cujas arestas têm comprimentos, ao lado de uma tabela de distâncias entre cada par de nós, com uma linha e uma coluna destacadas
Um pequeno grafo cujas arestas têm comprimentos, ao lado de uma tabela de distâncias entre cada par de nós, com uma linha e uma coluna destacadas

A ideia

O algoritmo de Dijkstra e o Bellman–Ford encontram as distâncias mais curtas a partir de uma origem. O Floyd–Warshall encontra-as de cada nó para todos os outros de uma só vez, numa tabela com uma linha e uma coluna por nó. Começa com o que as arestas dizem diretamente e depois melhora a tabela inteira, permitindo cada vez mais nós como escalas pelo caminho.

Passo a passo

Preencha a tabela: 0 de cada nó para si próprio, o comprimento da aresta entre vizinhos, e infinito no resto. Depois, para cada nó k e para cada par i, j: se a distância de i a k mais a distância de k a j for menor do que a distância de i a j, escreva o número menor. É o algoritmo todo. Em código são três ciclos, com k por fora.

Um exemplo

Tome quatro nós com as arestas A–B de comprimento 3, B–C 1, A–C 5 e C–D 2. A tabela começa com elas, e com infinito para A–D e B–D. A ronda A não muda nada, porque qualquer caminho por A é mais longo. A ronda B encontra de A a C através de B: 3 + 1 = 4, menos do que 5. A ronda C encontra de A a D através de C: 4 + 2 = 6, e de B a D: 1 + 2 = 3, ambos os primeiros caminhos encontrados. A ronda D não muda nada. A tabela final: A–B 3, A–C 4, A–D 6, B–C 1, B–D 3, C–D 2.

Porque é que a ordem dos ciclos importa

A escala k tem de ser o ciclo exterior. Depois da ronda de k, cada entrada é a distância mais curta usando como escalas apenas os primeiros k nós, e a ronda seguinte assenta nisso: um melhor caminho pela nova escala é um melhor caminho até ela mais um melhor caminho a partir dela, ambos já certos. Pôr k num ciclo interior quebra essa garantia e pode deixar distâncias erradas. Atualizar a tabela no próprio lugar durante uma ronda é seguro, porque a linha e a coluna do próprio k não mudam nessa ronda.

História e utilizações

Bernard Roy descreveu o método em 1959. Em 1962, Stephen Warshall publicou-o para o fecho transitivo, que só pergunta se um nó consegue chegar a outro, e Robert Floyd publicou-o para caminhos mais curtos. Calcula tabelas de distâncias e tabelas de encaminhamento, encontra o diâmetro de uma rede, diz que nós conseguem chegar a quais e, com uma entrada negativa na diagonal, revela um ciclo negativo.

Experimente

Abra a aplicação e prima Avançar. O grafo está de um lado e a tabela do outro. Cada ronda destaca a linha e a coluna da escala atual; cada passo escreve a distância mais curta de um par e contorna as duas entradas que foram somadas. As células que mudaram nesta ronda estão coloridas. Escolha uma origem e um destino para ver o caminho mais curto entre eles quando a tabela estiver completa.

Perguntas frequentes

Qual é a complexidade temporal do Floyd–Warshall?

O(n³) para n nós, seja qual for o número de arestas, e O(n²) de memória para a tabela. É o método preferido para grafos pequenos ou densos, onde o seu ciclo simples corre muito depressa.

Floyd–Warshall ou Dijkstra a partir de cada nó?

Para um grafo denso, ou quando as arestas podem ser negativas, o Floyd–Warshall é mais simples e quase tão rápido. Para um grafo grande e esparso com arestas não negativas, correr o algoritmo de Dijkstra a partir de cada nó é mais rápido.

O Floyd–Warshall é programação dinâmica?

Sim. Resolve o problema para caminhos com escalas entre os primeiros k nós usando as respostas para os primeiros k − 1 nós, e guarda uma só tabela, que vai reescrevendo.

O que é o fecho transitivo?

A tabela de que nós conseguem chegar a quais, sem olhar a distâncias. A versão de Warshall do algoritmo calcula-a com «ou» e «e» em vez de «min» e «+».

Pronto para experimentar?

Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.

Experimentar o Floyd–Warshall