O algoritmo que todo mundo aprende na faculdade e ninguém explica como usar de verdade
Você já deve ter visto o algoritmo de floyd-warshall em uma disciplina de estruturas de dados. A explicação padrão é curta: encontre o caminho mais curto entre todos os pares de vértices usando três loops aninhados com complexidade O(n³). Isso é tecnicamente correto e completamente inútil se você nunca tentou rodar isso em um grafo real. Eu passei uma semana inteira tentando diagnosticar por que uma rotina de roteirização interna começava a entregar tempos de resposta de minutos em vez de milissegundos quando o grafo passava de 500 nós. A causa era um uso cego do algoritmo clássico sem nenhuma adaptação prática. O problema não era o algoritmo em si. Era a suposição de que ele seria eficiente em qualquer situação.
Como funciona na prática
O algoritmo de floyd-warshall opera sobre uma matriz de distâncias onde cada célula representa o custo do caminho entre dois vértices. Você inicializa essa matriz com os pesos das arestas diretas e infinito para pares que não têm aresta. O algoritmo depois itera sobre cada vértice intermediário possível e atualiza a matriz verificando se passar por aquele vértice reduz o custo entre um par dado. O core é simples de entender, mas a implementação ingênua tem detalhes que causam dor de cabeça. Os três loops vão de k = 0 até n-1, i = 0 até n-1 e j = 0 até n-1. Dentro do loop mais interno, a atualização é:
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) Isso significa que, para cada vértice intermediário k, você testa se o caminho de i até j passando por k é menor que o melhor caminho conhecido. Quando todos os k foram processados, a matriz contém os caminhos mínimos entre todos os pares.
Eu descobri isso na marra quando uma execução testando rotas entre 1200 pontos começou a consumir 8GB de memória e levar cerca de 4 minutos. Meu primeiro palpite era otimizar a memória alocando uma matriz plana em vez de uma matriz bidimensional. Isso ajudou, mas não resolveu o problema central: o algoritmo não deveria ser rodado naquela escala para aqueles dados.
Pegadinhas que ninguém conta
O primeiro detalhe que você precisa saber é que o algoritmo clássico lida naturalmente com pesos negativos, mas não detecta ciclos negativos por si só. Se houver um ciclo negativo no grafo, a distância entre os vértices envolvidos nesse ciclo tende a menos infinito. Em implementações comuns, você simplesmente verifica os elementos da diagonal após a execução. Se algum valor for negativo, existe um ciclo negativo no grafo. Sem esse check, você pode terminar com resultados que parecem válidos mas estão completamente corrompidos. O segundo detalhe é a questão da representação de infinito. Usar um número extremamente grande como infinito, como Integer.MAX_VALUE ou 1e18, é perigoso. Se você adicionar esse valor a si mesmo durante uma atualização, acontece estouro numérico e o resultado fica incorreto. A solução prática que eu adotei foi usar Optional ou sentinelas distintas, ou simplesmente limitar a faixa de valores válidos. Em Python, por exemplo, usar float('inf') evita estouro, mas em C++ com tipos fixos, ter cuidado com somas que incluem infinito é obrigatório.
👉 Clique no botão abaixo para saber mais sobre o assunto!
A questão mais importante que quase ninguém menciona é a densidade. Se seu grafo for esparso, o Floyd-Warshall é frequentemente uma péssima escolha. Rodar O(n³) quando sua matriz esparsa tem apenas algumas arestas ativas é desperdício puro. Nesses casos, rodar Dijkstra a partir de cada vértice de origem tem complexidade O(n · (E + V log V)) com heap de Fibonacci ou O(n · E log V) com heap binário, o que costuma ser drasticamente menor em grafos esparsos. Eu vi casos práticos onde grafos com 2000 vértices e aproximadamente 5000 arestas processavam Dijkstra múltiplo em menos de 10 segundos, enquanto o Floyd-Warshall clássico levava mais de 3 minutos.
Ciclos negativos e o problema que me pegou
Certa vez, eu estava trabalhando em um sistema de simulação de fluxo de dados onde os pesos podiam ser tanto positivos quanto negativos dependendo do tipo de operação. Um módulo particular introduzia um ciclo de peso -2 entre três nós devido a uma condição de competição mal modelada. O algoritmo de floyd-warshall rodou até o fim sem nenhuma mensagem de erro. A matriz final continha valores cada vez menores na diagonal para aqueles três vértices, indicando claramente o ciclo negativo, mas meu código de validação simplesmente verificava se havia infinito na matriz e ignorava completamente a diagonal. O workaround foi direto: após cada iteração completa de k, eu adicionava uma verificação adicional percorrendo a diagonal e marcando os vértices com distância negativa. Qualquer vértice atingido por um desses nós entra em propagação infinita, então eu os exclui dos resultados finais. Isso adicionou O(n) por iteração externa, ou seja, O(n²) total, o que é desprezível em comparação com o O(n³) principal.
Quando usar e quando fugir
O algoritmo de floyd-warshall faz sentido quando você precisa de caminhos mínimos entre todos os pares, o grafo tem no máximo algumas centenas de vértices, e os pesos são pequenos o suficiente para não causar problemas de estouro. Ele também é útil quando o grafo é denso, pois a diferença de complexidade entre ele e múltiplas execuções de Dijkstra diminui. A matriz de adjacência fica toda na memória de forma contígua, o que favorece o cache do processador e torna o acesso rápido. Se seu grafo tem mais de mil vértices e é esparso, considere múltiplas execuções de Dijkstra. Se precisa apenas de caminhos entre um par específico, use Dijkstra simples com uma única fonte e destino. Se trabalha com grafos dinâmicos onde arestas são adicionadas e removidas frequentemente, pense em algoritmos de atualização incremental, pois recalcular tudo do zero a cada mudança é ineficiente.
Em termos de performance prática, para um grafo com 300 vértices, o Floyd-Warshall roda em torno de 0,02 a 0,05 segundos em hardware moderno. Para 500 vértices, cerca de 0,12 a 0,25 segundos. Para 1000 vértices, algo entre 1 e 2 segundos. Para 2000 vértices, a ordem de grandeza salta para 8 a 15 segundos, e aí começa a fazer sentido migrar para outra abordagem.
Implementação básica
Uma implementação direta em Python se parece com isso: def floyd_warshall(distancia, vertices):
for k in range(vertices):
, for i in range(vertices):
, for j in range(vertices):
, if distancia[i][k] + distancia[k][j] < distancia[i][j]:
, distancia[i][j] = distancia[i][k] + distancia[k][j]
Onde a matriz inicial já contém as arestas e infinito para pares não conectados. A recuperação do predecessor pode ser feita mantendo uma matriz separa que armazena o penúltimo vértice em cada caminho mínimo, permitindo reconstruir o caminho exato entre qualquer par. O algoritmo de floyd-warshall é uma ferramenta sólida quando aplicada corretamente. O erro mais comum é usá-lo como solução universal para todos os problemas de caminhos mínimos sem considerar a densidade do grafo e o tamanho dos dados. Conhecer seus limites evita muito tempo perdido com otimizações que seriam desnecessárias se a escolha do algoritmo tivesse sido feita direito desde o início.
