--- title: "Algoritmo de Floyd-Warshall em Rust" url: "https://rustlang.com.br/algoritmos/floyd-warshall/" markdown_url: "https://rustlang.com.br/algoritmos/floyd-warshall.MD" description: "Implementação completa do algoritmo de Floyd-Warshall em Rust: todos os pares de caminhos mínimos, detecção de ciclos negativos e diagramas visuais." date: "2026-02-24" author: "Equipe Rust Brasil" --- # Algoritmo de Floyd-Warshall em Rust Implementação completa do algoritmo de Floyd-Warshall em Rust: todos os pares de caminhos mínimos, detecção de ciclos negativos e diagramas visuais. 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](/algoritmos/dijkstra/) e do [Bellman-Ford](/algoritmos/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). ```rust 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> { 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 ```rust const INF: i64 = i64::MAX / 2; /// Executa Floyd-Warshall e retorna a matriz de distâncias mínimas. fn floyd_warshall(dist: &mut Vec>) { 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>) -> 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>, 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 ```rust 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>>) { 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![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>>, dist: &Vec>, origem: usize, destino: usize, ) -> Option> { 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: ```rust // Após executar Floyd-Warshall na matriz dist: let vertices_em_ciclo: Vec = (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: ```rust fn fecho_transitivo(adjacente: &Vec>) -> Vec> { 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](/algoritmos/dijkstra/) V vezes é mais eficiente. - Precisa de distâncias a partir de **uma única fonte** — use [Dijkstra](/algoritmos/dijkstra/) ou [Bellman-Ford](/algoritmos/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 1. **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. 2. **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). 3. **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. 4. **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](/stdlib/vec/) — para matrizes de distância (Vec>) - [`Arrays` — Arrays de tamanho fixo](/stdlib/arrays/) — para matrizes quando V é conhecido em tempo de compilação - [`Option` — Tipo opcional](/stdlib/option/) — para representar caminhos inexistentes - [`Tipos numéricos`](/stdlib/tipos-numericos/) — para escolher o tipo adequado de peso (i64, f64) - [Algoritmo de Dijkstra](/algoritmos/dijkstra/) — caminho mínimo de fonte única (sem pesos negativos) - [Algoritmo de Bellman-Ford](/algoritmos/bellman-ford/) — caminho mínimo de fonte única (com pesos negativos) - [Busca em Largura (BFS)](/algoritmos/bfs/) — caminho mínimo em grafos sem peso