Floyd-Warshall: caminhos mínimos entre todos os pares

Floyd-Warshall calcula os caminhos mais curtos entre cada par de nós em um grafo ponderado — inclusive em grafos com pesos negativos nas arestas (mas não com ciclos negativos). Executar Dijkstra a partir de cada origem leva O(V × (V+E) log V); Floyd-Warshall é executado em O(V³), independentemente da densidade das arestas. Para grafos densos com V ≤ 500, Floyd-Warshall costuma ser mais simples e ter velocidade comparável.

A ideia central de Floyd-Warshall: dp[i][j][k] = caminho mais curto de i até j usando apenas os nós {0, 1, ..., k} como intermediários. Ou o caminho mais curto usa o nó k como intermediário, ou não usa. Se usar: dp[i][j][k] = dp[i][k][k-1] + dp[k][j][k-1]. Se não usar: dp[i][j][k] = dp[i][j][k-1]. Como a terceira dimensão avança apenas para frente, ela pode ser eliminada — atualizamos no próprio local.

Comece com uma matriz V×V: dist[i][i] = 0 (distância até si próprio igual a zero), dist[i][j] = weight para arestas diretas e dist[i][j] = inf para pares sem aresta. Em seguida, percorra todos os nós intermediários k, atualizando os pares (i, j). O laço externo sobre k deve vir primeiro para que os caminhos através de um conjunto crescente de intermediários permitidos sejam construídos corretamente.

Vamos acompanhar o Floyd-Warshall em um grafo com 4 nós. Depois de processar cada nó intermediário k, a matriz é preenchida com caminhos mais curtos que passam por k. O algoritmo trata naturalmente vários saltos ao construir os caminhos mais curtos de forma incremental.

Depois de executar Floyd-Warshall, verifique a diagonal principal: se algum dist[i][i] < 0, existe um ciclo negativo que passa pelo nó i. Isso ocorre porque um ciclo negativo permite chegar a i partindo de i com custo negativo. Se não existir nenhum ciclo negativo, todas as entradas da diagonal permanecerão iguais a 0.

Para reconstruir o caminho real de i até j, mantenha uma matriz next[i][j]: inicialmente, next[i][j] = j para arestas diretas. Ao atualizar através do intermediário k, defina next[i][j] = next[i][k]. Para recuperar o caminho: comece em i e siga os ponteiros de next até chegar a j. Isso acrescenta espaço O(V²) e O(V) por reconstrução de caminho.

Uma variante mais simples: o fecho transitivo responde à pergunta “o nó j é alcançável a partir do nó i?” para todos os pares. Substitua as distâncias por valores booleanos: reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j]). Isso é Floyd-Warshall usando OR booleano em vez de adição e mínimo. Inicialize reach[i][i] = True e reach[i][j] = True para arestas diretas.

Floyd-Warshall: O(V³) de tempo, O(V²) de espaço. Para grafos densos (E ≈ V²) com V ≤ 300, ele é mais rápido que executar Dijkstra V vezes (também O(V³ nesse caso). Para grafos esparsos com V = 1000 e E = 3000, V execuções de Dijkstra custam O(V×E×log V) ≈ 33M, enquanto Floyd-Warshall custa O(V³) = 10⁹ — Dijkstra vence. Saiba quando cada um é apropriado.

Defina todos os pesos das arestas como 1 (ou use uma matriz de adjacência booleana com Floyd-Warshall, usando soma em vez de mínimo): dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). Isso calcula o número mínimo de saltos entre todos os pares — um resultado de BFS entre todos os pares, mas calculado com uma única passagem de Floyd-Warshall de O(V³).

Floyd-Warshall aparece em entrevistas em questões que envolvem: (1) distâncias entre todos os pares em um grafo pequeno, (2) verificar se existe algum ciclo com peso total negativo, (3) calcular caminhos mais curtos em problemas de propagação de restrições e (4) problemas que pedem explicitamente soluções O(V³), em que V ≤ 200. Mencione sempre a estrutura de três laços e o requisito de não haver ciclos negativos para garantir a correção.

Para grafos não direcionados, adicione as duas direções para cada aresta: dist[u][v] = dist[v][u] = weight. O restante do algoritmo é idêntico. A matriz resultante é simétrica: dist[i][j] == dist[j][i] para todos os pares. Ao inicializar, tome cuidado para não atribuir acidentalmente arestas direcionais — as arestas não direcionadas devem ser adicionadas nas duas direções à matriz inicial antes da execução dos três laços.

Nesta lição, você aprendeu que: Floyd-Warshall calcula os caminhos mais curtos entre todos os pares com três laços aninhados e a recorrência dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]), os ciclos negativos podem ser detectados verificando se algum dist[i][i] < 0 após a conclusão e o algoritmo é executado em tempo O(V³) e espaço O(V²). Em seguida, retomaremos as aplicações de caminhos mais curtos com Network Delay Time e técnicas de reconstrução de caminhos.