Devolva o grafo e receba uma matriz de distâncias
O algoritmo de floyd-warshall é basicamente três loops aninhados que atualizam uma matriz de distâncias. Nada mais. A ideia central é simples o suficiente para caber num post de fórum, mas a implementação que você vai achar na internet tem uma armadilha que quase ninguém menciona até cometer o erro na mão.
algoritmo de floyd-warshall na prática
Comece com uma matriz n x n preenchida com infinito para arestas inexistentes e zero na diagonal. O loop externo itera sobre cada vértice intermediário k. Os dois internos verificam se ir de i para j passando por k é mais barato do que a distância já conhecida. Se for, atualiza.
for k in range(n):
for i in range(n):
for j in range(n):
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
É isso. A complexidade é O(n³) e o espaço é O(n²). Para grafos com até algumas centenas de vértices funciona sem dor de cabeça. Acima disso, você já está pedindo problemas de memória. Uma coisa que não ensinam nos tutoriais: você pode otimizar o loop interno usando uma versão em linha. Em Python puro, isso costuma cortar o tempo de execução pela metade em comparação com a implementação ingênua dos três loops, porque evita a sobrecarga de acesso multidimensional repetido. O resultado final é idêntico, só que roda mais rápido.
👉 Clique no botão abaixo para saber mais sobre o assunto!
Ciclos negativos: onde tudo dá errado
A parte que mais causa dor de cabeça é detectar ciclos negativos. Se houver um ciclo negativo no grafo, a diagonal da matriz resultante terá valores negativos. Mas cuidado: esse teste só funciona se o algoritmo executar até o final. Parar antes e verificar no meio do caminho dá resultados incorretos porque a propagação ainda não stabilizou. No meu caso, trabalhei num projeto de roteirização logística onde o grafo tinha arestas com peso negativo vindas de reembolsos e ajustes contratuais. O código original simplesmente pegava o resultado da matriz e usava os valores mais baixos sem verificar ciclos. A resposta vinha errada há dois dias e ninguém entendia por quê. A solução foi rodar uma iteração extra depois dos três loops principais e verificar se algum valor na matriz ainda podia ser reduzido. Se sim, ciclo negativo existe. Esse passo extra é barateiro e evita horas de depuração.
Quando não usar
Se seu grafo for espars com milhões de vértices e poucas arestas, Floyd-Warshall é a pior escolha possível. A complexidade cúbica torna o algoritmo impraticável. Nesse cenário, execute Dijkstra a partir de cada vértice fonte, ou use Johnson's algorithm se houver pesos negativos mas nenhum ciclo negativo. Ambos combinam melhor com grafos esparsos. Também não use quando precisar recuperar o caminho mínimo real, não apenas a distância. O algoritmo padrão só retorna números. Você precisará manter uma matriz de predecessoros separada e reconstruir o caminho manualmente depois, o que dobra o trabalho de implementação e o espaço em memória.
Exemplo concreto
Pegue um grafo com quatro vértices e arestas pesadas entre alguns deles mas incompletas entre outros. Preencha a matriz inicial com os pesos diretos e infinito nas posições sem aresta. Rode os três loops. No final, a célula dist[0][3] vai conter o menor custo de ir do vértice 0 ao vértice 3, considerando todos os caminhos possíveis. Um detalhe prático: weights iguais a zero são perfeitamente válidos e não representam arestas inexistentes. Confundir zero com infinito é um erro comum que gera resultados completamente errados sem aviso algum.
Código pronto
Você encontra implementações em praticamente qualquer repositório de algoritmos. Procure por "floyd warshall python" ou "floyd warshall c++" no GitHub e filtre por estrelas. A maioria das bibliotecas como NetworkX já incluem a função pronta, mas saber a implementação por baixo ajuda a diagnosticar quando o resultado não faz sentido.
