O algoritmo de Floyd-Warshall encontra o caminho mais curto entre todos os pares de vértices de um grafo ponderado em uma única execução. Diferente do Dijkstra e do Bellman-Ford, que calculam distâncias a partir de uma única fonte, o Floyd-Warshall resolve o problema completo: para cada par (i, j), qual é a menor distância de i a j? O algoritmo também suporta arestas com peso negativo e pode detectar ciclos negativos.
Na prática, o Floyd-Warshall é usado quando precisamos de uma matriz completa de distâncias — por exemplo, em sistemas de navegação que pré-calculam rotas entre todas as cidades, em análise de redes sociais (distância entre quaisquer dois usuários), em jogos para pré-computar distâncias entre pontos de interesse, e em otimização de logística quando o número de pontos é relativamente pequeno (centenas, não milhares).
Como Funciona
O Floyd-Warshall usa programação dinâmica com a seguinte ideia: para cada vértice intermediário k, verifica se o caminho de i a j passando por k é mais curto que o melhor caminho conhecido.
A recorrência é:
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
O algoritmo tem três loops aninhados: o loop externo itera sobre cada possível vértice intermediário k, e os dois loops internos iteram sobre todos os pares (i, j).
Ordem crucial dos loops: o loop de k DEVE ser o mais externo. Isso garante que, quando consideramos k como intermediário, já temos os melhores caminhos usando intermediários 0, 1, ..., k-1.
Diagrama Visual — Atualização da Matriz de Distâncias
Grafo de exemplo:
(0) ---3---> (1)
| / |
| / |
8| 1/ -4|
| / |
v v v
(2) ---2---> (3)
^ |
| |
\---7--------/
Arestas: 0->1:3, 0->2:8, 1->2:1, 1->3:-4, 2->3:2, 3->2:7
Matriz de distância inicial (INF = sem aresta direta):
| 0 1 2 3
-----|--------------------
0 | 0 3 8 INF
1 | INF 0 1 -4
2 | INF INF 0 2
3 | INF INF 7 0
Execução passo a passo:
=== k = 0 (usando vértice 0 como intermediário) ===
Verifica todos os pares (i,j): algum caminho melhora passando por 0?
- dist[1][2] = min(1, INF + 8) = 1 (sem melhoria)
- dist[2][1] = min(INF, INF + 3) = INF (sem melhoria)
- Nenhuma melhoria com k=0
| 0 1 2 3
-----|--------------------
0 | 0 3 8 INF
1 | INF 0 1 -4
2 | INF INF 0 2
3 | INF INF 7 0
=== k = 1 (usando vértice 1 como intermediário) ===
- dist[0][2] = min(8, 3 + 1) = 4 (melhoria! 0->1->2)
- dist[0][3] = min(INF, 3 + (-4)) = -1 (melhoria! 0->1->3)
| 0 1 2 3
-----|--------------------
0 | 0 3 [4] [-1]
1 | INF 0 1 -4
2 | INF INF 0 2
3 | INF INF 7 0
=== k = 2 (usando vértice 2 como intermediário) ===
- dist[0][3] = min(-1, 4 + 2) = -1 (sem melhoria)
- dist[1][3] = min(-4, 1 + 2) = -4 (sem melhoria)
- dist[3][0] = min(INF, 7 + INF) = INF (sem melhoria)
| 0 1 2 3
-----|--------------------
0 | 0 3 4 -1
1 | INF 0 1 -4
2 | INF INF 0 2
3 | INF INF 7 0
=== k = 3 (usando vértice 3 como intermediário) ===
- dist[0][2] = min(4, -1 + 7) = 4 (sem melhoria: 6 > 4)
- dist[1][2] = min(1, -4 + 7) = 1 (sem melhoria: 3 > 1)
- dist[2][0] = min(INF, 2 + INF) = INF (sem melhoria)
| 0 1 2 3
-----|--------------------
0 | 0 3 4 -1
1 | INF 0 1 -4
2 | INF INF 0 2
3 | INF INF 7 0
Resultado final: a matriz contém as distâncias mínimas entre todos os pares.
Representação do Grafo
Para Floyd-Warshall, a representação natural é uma matriz de adjacência (ou matriz de distâncias).
const INF: i64 = i64::MAX / 2; // Evita overflow na soma
/// Cria a matriz de distâncias iniciais.
/// dist[i][j] = peso da aresta i->j, ou INF se não houver aresta.
fn criar_matriz_distancias(num_vertices: usize, arestas: &[(usize, usize, i64)]) -> Vec<Vec<i64>> {
let mut dist = vec![vec![INF; num_vertices]; num_vertices];
// Distância de cada vértice a si mesmo é 0
for i in 0..num_vertices {
dist[i][i] = 0;
}
// Preenche com as arestas
for &(u, v, peso) in arestas {
dist[u][v] = peso;
}
dist
}
Complexidade
| Caso | Tempo | Espaço |
|---|---|---|
| Melhor | O(V^3) | O(V^2) |
| Médio | O(V^3) | O(V^2) |
| Pior | O(V^3) | O(V^2) |
Onde V = número de vértices.
- Tempo O(V^3): três loops aninhados de 0 a V-1, cada um fazendo trabalho O(1).
- Espaço O(V^2): a matriz de distâncias V x V (pode ser feito in-place, sem matriz auxiliar).
- A complexidade é fixa — não depende do número de arestas. Isso torna o Floyd-Warshall ideal para grafos densos e problemático para grafos esparsos grandes.
- Para grafos esparsos, executar Dijkstra V vezes (O(V * (V + E) log V)) pode ser mais eficiente.
Implementação em Rust
Floyd-Warshall Básico
const INF: i64 = i64::MAX / 2;
/// Executa Floyd-Warshall e retorna a matriz de distâncias mínimas.
fn floyd_warshall(dist: &mut Vec<Vec<i64>>) {
let n = dist.len();
// k DEVE ser o loop mais externo
for k in 0..n {
for i in 0..n {
for j in 0..n {
if dist[i][k] + dist[k][j] < dist[i][j] {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
}
/// Verifica se há ciclo negativo (dist[i][i] < 0 para algum i).
fn tem_ciclo_negativo(dist: &Vec<Vec<i64>>) -> bool {
for i in 0..dist.len() {
if dist[i][i] < 0 {
return true;
}
}
false
}
fn main() {
let arestas = [
(0, 1, 3i64), (0, 2, 8), (1, 2, 1),
(1, 3, -4), (2, 3, 2), (3, 2, 7),
];
let n = 4;
let mut dist = vec![vec![INF; n]; n];
for i in 0..n {
dist[i][i] = 0;
}
for &(u, v, peso) in &arestas {
dist[u][v] = peso;
}
println!("Matriz inicial:");
imprimir_matriz(&dist, n);
floyd_warshall(&mut dist);
if tem_ciclo_negativo(&dist) {
println!("\nCiclo negativo detectado!");
} else {
println!("\nMatriz de distâncias mínimas:");
imprimir_matriz(&dist, n);
}
}
fn imprimir_matriz(dist: &Vec<Vec<i64>>, n: usize) {
print!(" ");
for j in 0..n {
print!("{:>6}", j);
}
println!();
println!(" {}", "-".repeat(n * 6));
for i in 0..n {
print!(" {} |", i);
for j in 0..n {
if dist[i][j] >= INF / 2 {
print!(" INF");
} else {
print!("{:>6}", dist[i][j]);
}
}
println!();
}
}
// Saída:
// Matriz de distâncias mínimas:
// 0 1 2 3
// ----------------------------
// 0 | 0 3 4 -1
// 1 | INF 0 1 -4
// 2 | INF INF 0 2
// 3 | INF INF 7 0
Floyd-Warshall com Reconstrução de Caminho
const INF: i64 = i64::MAX / 2;
/// Executa Floyd-Warshall com reconstrução de caminho.
/// Retorna (matriz de distâncias, matriz de próximo vértice no caminho).
fn floyd_warshall_com_caminho(
num_vertices: usize,
arestas: &[(usize, usize, i64)],
) -> (Vec<Vec<i64>>, Vec<Vec<Option<usize>>>) {
let n = num_vertices;
let mut dist = vec![vec![INF; n]; n];
// proximo[i][j] = próximo vértice no caminho de i a j
let mut proximo: Vec<Vec<Option<usize>>> = vec![vec![None; n]; n];
// Inicialização
for i in 0..n {
dist[i][i] = 0;
proximo[i][i] = Some(i);
}
for &(u, v, peso) in arestas {
dist[u][v] = peso;
proximo[u][v] = Some(v);
}
// Floyd-Warshall
for k in 0..n {
for i in 0..n {
for j in 0..n {
if dist[i][k] + dist[k][j] < dist[i][j] {
dist[i][j] = dist[i][k] + dist[k][j];
proximo[i][j] = proximo[i][k];
}
}
}
}
(dist, proximo)
}
/// Reconstrói o caminho de `origem` a `destino`.
fn reconstruir_caminho(
proximo: &Vec<Vec<Option<usize>>>,
dist: &Vec<Vec<i64>>,
origem: usize,
destino: usize,
) -> Option<Vec<usize>> {
if dist[origem][destino] >= INF / 2 {
return None; // Sem caminho
}
let mut caminho = vec![origem];
let mut atual = origem;
while atual != destino {
match proximo[atual][destino] {
Some(prox) => {
atual = prox;
caminho.push(atual);
}
None => return None,
}
}
Some(caminho)
}
fn main() {
let arestas = [
(0, 1, 3i64), (0, 2, 8), (1, 2, 1),
(1, 3, -4), (2, 3, 2), (3, 2, 7),
];
let (dist, proximo) = floyd_warshall_com_caminho(4, &arestas);
// Mostra caminhos mínimos entre todos os pares
let nomes = ["A", "B", "C", "D"];
for i in 0..4 {
for j in 0..4 {
if i == j {
continue;
}
if let Some(caminho) = reconstruir_caminho(&proximo, &dist, i, j) {
let caminho_str: Vec<&str> = caminho.iter().map(|&v| nomes[v]).collect();
println!(
"{} -> {} (dist={}): {}",
nomes[i],
nomes[j],
dist[i][j],
caminho_str.join(" -> ")
);
} else {
println!("{} -> {}: sem caminho", nomes[i], nomes[j]);
}
}
}
// Saída:
// A -> B (dist=3): A -> B
// A -> C (dist=4): A -> B -> C
// A -> D (dist=-1): A -> B -> D
// B -> A: sem caminho
// B -> C (dist=1): B -> C
// B -> D (dist=-4): B -> D
// C -> A: sem caminho
// C -> B: sem caminho
// C -> D (dist=2): C -> D
// D -> A: sem caminho
// D -> B: sem caminho
// D -> C (dist=7): D -> C
}
Detecção de Ciclo Negativo
Após executar o Floyd-Warshall, basta verificar a diagonal da matriz: se dist[i][i] < 0 para algum vértice i, então esse vértice faz parte de um ciclo negativo. Os vértices afetados podem ser coletados iterando a diagonal:
// Após executar Floyd-Warshall na matriz dist:
let vertices_em_ciclo: Vec<usize> = (0..n)
.filter(|&i| dist[i][i] < 0)
.collect();
Exemplo de Execução
Rede de entregas entre 4 centros de distribuição com custos e bonificações:
Centros: SP(0), RJ(1), BH(2), Curitiba(3)
Custos (positivo = custo, negativo = bonificação do trecho):
SP->RJ: 5 SP->BH: 10 SP->Curitiba: 3
RJ->BH: 2 RJ->Curitiba: 8
BH->Curitiba: 1 BH->SP: -2 (bonificação)
Curitiba->RJ: 4
Matriz inicial:
| SP RJ BH CWB
-----|-------------------------
SP | 0 5 10 3
RJ | INF 0 2 8
BH | -2 INF 0 1
CWB | INF 4 INF 0
k=0: BH->RJ = 3 (via SP)
k=1: SP->BH = 7 (via RJ), CWB->BH = 6 (via RJ)
k=2: RJ->SP = 0 (via BH), RJ->CWB = 3 (via BH), CWB->SP = 4 (via BH)
k=3: Nenhuma melhoria.
Resultado final:
| SP RJ BH CWB
-----|-------------------------
SP | 0 5 7 3
RJ | 0 0 2 3
BH | -2 3 0 1
CWB | 4 4 6 0
Variações e Otimizações
1. Floyd-Warshall para Fecho Transitivo
Para determinar apenas se existe caminho entre cada par (sem calcular distâncias), use uma versão booleana:
fn fecho_transitivo(adjacente: &Vec<Vec<bool>>) -> Vec<Vec<bool>> {
let n = adjacente.len();
let mut alcancavel = adjacente.clone();
for i in 0..n {
alcancavel[i][i] = true;
}
for k in 0..n {
for i in 0..n {
for j in 0..n {
alcancavel[i][j] = alcancavel[i][j]
|| (alcancavel[i][k] && alcancavel[k][j]);
}
}
}
alcancavel
}
2. Floyd-Warshall com Minimax / Maximin
Em vez de somar pesos, use min e max para encontrar o caminho minimax (minimizar o peso máximo de aresta no caminho) ou maximin (maximizar o peso mínimo). Útil para problemas de gargalo em redes.
3. Otimização de Memória
Se não precisa de reconstrução de caminho, a matriz de distâncias pode ser atualizada in-place sem memória adicional. Para grafos muito grandes, considere representações esparsas.
Quando Usar
Use Floyd-Warshall quando:
- Precisa das distâncias entre todos os pares de vértices.
- O grafo é denso (muitas arestas) ou relativamente pequeno (V <= 500-1000).
- O grafo pode ter arestas com peso negativo (mas sem ciclos negativos, ou quer detectá-los).
- A simplicidade de implementação é prioridade (apenas 3 loops aninhados).
- Precisa do fecho transitivo do grafo.
- Precisa de caminhos minimax ou maximin.
Evite Floyd-Warshall quando:
- O grafo é grande e esparso — executar Dijkstra V vezes é mais eficiente.
- Precisa de distâncias a partir de uma única fonte — use Dijkstra ou Bellman-Ford.
- V > 1000 — O(V^3) se torna proibitivo.
Comparação com Outros Algoritmos
| Característica | Floyd-Warshall | Dijkstra (V vezes) | Bellman-Ford (V vezes) | Johnson |
|---|---|---|---|---|
| Problema resolvido | Todos os pares | Todos os pares | Todos os pares | Todos os pares |
| Pesos negativos | Sim | Nao | Sim | Sim |
| Detecção ciclo negativo | Sim | Nao | Sim | Sim |
| Complexidade de tempo | O(V^3) | O(V(V+E) log V) | O(V^2 * E) | O(VE + V^2 log V) |
| Complexidade de espaço | O(V^2) | O(V + E) | O(V) | O(V^2) |
| Melhor para grafos densos | Sim | Nao | Nao | Nao |
| Melhor para grafos esparsos | Nao | Sim | Nao | Sim |
| Simplicidade | Muito simples | Moderada | Simples | Complexa |
Exercícios Práticos
Matriz de distâncias de cidades: Dadas N cidades com estradas bidirecionais e distâncias, calcule a matriz completa de distâncias mínimas. Imprima a tabela formatada e o caminho entre cada par.
Fecho transitivo: Dado um grafo direcionado representando “quem segue quem” em uma rede social, determine para cada par de usuários se existe uma cadeia de seguimento (direta ou indireta).
Diâmetro do grafo: Use Floyd-Warshall para encontrar o diâmetro de um grafo — a maior distância mínima entre quaisquer dois vértices. Identifique o par de vértices mais distante.
Caminho minimax: Em uma rede de estradas com limites de peso (cada aresta tem um peso máximo de veículo), encontre para cada par de cidades o caminho que permite o veículo mais pesado (maximizar o mínimo peso permitido ao longo do caminho).
Veja Também
Vec— Vetor dinâmico — para matrizes de distância (Vec<Vec>) Arrays— Arrays de tamanho fixo — para matrizes quando V é conhecido em tempo de compilaçãoOption— Tipo opcional — para representar caminhos inexistentesTipos numéricos— para escolher o tipo adequado de peso (i64, f64)- Algoritmo de Dijkstra — caminho mínimo de fonte única (sem pesos negativos)
- Algoritmo de Bellman-Ford — caminho mínimo de fonte única (com pesos negativos)
- Busca em Largura (BFS) — caminho mínimo em grafos sem peso