--- title: "Bellman-Ford em Zig: Caminho Mínimo e Ciclos Negativos" url: "https://ziglang.com.br/algoritmos/bellman-ford/" markdown_url: "https://ziglang.com.br/algoritmos/bellman-ford.MD" description: "Implemente Bellman-Ford em Zig para calcular caminhos mínimos com pesos negativos, detectar ciclos negativos e reconstruir rotas com segurança." date: "2026-08-21" author: "Zig Brasil" --- # Bellman-Ford em Zig: Caminho Mínimo e Ciclos Negativos Implemente Bellman-Ford em Zig para calcular caminhos mínimos com pesos negativos, detectar ciclos negativos e reconstruir rotas com segurança. # Bellman-Ford em Zig: Caminho Mínimo e Ciclos Negativos O **algoritmo de Bellman-Ford** encontra o caminho de menor custo entre um vértice de origem e todos os demais vértices de um grafo ponderado. Sua principal vantagem é aceitar **arestas com peso negativo** e detectar **ciclos negativos alcançáveis pela origem**. Em Zig, uma implementação clara usa uma lista de arestas, um slice de distâncias e outro de predecessores, com complexidade **O(V × E)**. A recomendação direta é: use Bellman-Ford quando pesos negativos forem parte legítima do modelo ou quando a detecção de ciclos negativos for um requisito. Se todos os pesos forem não negativos, Dijkstra normalmente oferece desempenho melhor. Se você precisa das distâncias entre todos os pares de vértices, compare com o [algoritmo de Floyd-Warshall em Zig](/algoritmos/floyd-warshall/). ## Resposta rápida | Pergunta | Resposta | |---|---| | O que Bellman-Ford calcula? | menor distância da origem para cada vértice | | Aceita pesos negativos? | sim | | Detecta ciclos negativos? | sim, quando são alcançáveis pela origem | | Complexidade de tempo | O(V × E) | | Espaço auxiliar | O(V) | | Estrutura mais simples | lista de arestas | | Melhor alternativa sem pesos negativos | Dijkstra | | Melhor alternativa para todos os pares | Floyd-Warshall | | Otimização básica | parar quando uma rodada não altera distâncias | Bellman-Ford aparece em roteamento, arbitragem, análise de dependências e problemas nos quais uma transição pode reduzir o custo acumulado. O algoritmo também é útil como ferramenta de validação: mesmo quando a aplicação não espera pesos negativos, detectar um ciclo desse tipo pode revelar dados inconsistentes. ## Como o algoritmo funciona Considere um grafo direcionado com uma distância provisória para cada vértice. No início, a origem recebe distância zero e os demais vértices recebem infinito. Para cada aresta `u → v` com peso `w`, Bellman-Ford testa a operação chamada **relaxamento**: ```text se dist[u] + w < dist[v]: dist[v] = dist[u] + w predecessor[v] = u ``` Uma rota simples pode ter no máximo `V - 1` arestas, pois repetir um vértice formaria um ciclo. Por isso, o algoritmo percorre todas as arestas até `V - 1` vezes. A cada rodada, caminhos com mais uma aresta podem ser propagados. Depois dessas rodadas, uma passagem adicional testa todas as arestas. Se ainda for possível reduzir uma distância, existe um ciclo de peso negativo alcançável pela origem. Dar mais voltas nesse ciclo reduziria o custo indefinidamente, portanto não existe uma menor distância finita para os vértices afetados. ## Exemplo passo a passo Considere estas arestas: ```text 0 → 1 peso 4 0 → 2 peso 5 1 → 2 peso -2 2 → 3 peso 3 1 → 3 peso 6 ``` As distâncias iniciais são: ```text [0, ∞, ∞, ∞] ``` Ao relaxar `0 → 1`, a distância de `1` passa a `4`. A aresta `0 → 2` atribui `5` a `2`. Em seguida, `1 → 2` melhora o resultado de `5` para `2`, porque `4 + (-2) = 2`. Por fim, `2 → 3` produz distância `5`. O resultado é: ```text vértice: 0 1 2 3 distância: 0 4 2 5 ``` O caminho até `3` é `0 → 1 → 2 → 3`, não `0 → 1 → 3`. O peso negativo não representa um erro por si só; ele apenas exige um algoritmo que não finalize um vértice cedo demais. ## Implementação de Bellman-Ford em Zig A lista de arestas combina naturalmente com o algoritmo, pois cada rodada precisa visitar todas elas. O código abaixo separa o resultado, a execução e a reconstrução do caminho. ```zig const std = @import("std"); const Allocator = std.mem.Allocator; const Aresta = struct { origem: usize, destino: usize, peso: i64, }; const INF = std.math.maxInt(i64); const Resultado = struct { distancias: []i64, predecessores: []?usize, tem_ciclo_negativo: bool, allocator: Allocator, pub fn deinit(self: *Resultado) void { self.allocator.free(self.distancias); self.allocator.free(self.predecessores); } }; fn somarSemOverflow(a: i64, b: i64) ?i64 { return std.math.add(i64, a, b) catch null; } pub fn bellmanFord( allocator: Allocator, numero_de_vertices: usize, arestas: []const Aresta, origem: usize, ) !Resultado { if (origem >= numero_de_vertices) return error.VerticeInvalido; for (arestas) |aresta| { if (aresta.origem >= numero_de_vertices or aresta.destino >= numero_de_vertices) { return error.VerticeInvalido; } } const distancias = try allocator.alloc(i64, numero_de_vertices); errdefer allocator.free(distancias); const predecessores = try allocator.alloc(?usize, numero_de_vertices); errdefer allocator.free(predecessores); @memset(distancias, INF); @memset(predecessores, null); distancias[origem] = 0; if (numero_de_vertices > 1) { for (0..numero_de_vertices - 1) |_| { var alterou = false; for (arestas) |aresta| { const distancia_origem = distancias[aresta.origem]; if (distancia_origem == INF) continue; const candidata = somarSemOverflow( distancia_origem, aresta.peso, ) orelse return error.OverflowDeDistancia; if (candidata < distancias[aresta.destino]) { distancias[aresta.destino] = candidata; predecessores[aresta.destino] = aresta.origem; alterou = true; } } if (!alterou) break; } } var tem_ciclo_negativo = false; for (arestas) |aresta| { const distancia_origem = distancias[aresta.origem]; if (distancia_origem == INF) continue; const candidata = somarSemOverflow( distancia_origem, aresta.peso, ) orelse return error.OverflowDeDistancia; if (candidata < distancias[aresta.destino]) { tem_ciclo_negativo = true; break; } } return .{ .distancias = distancias, .predecessores = predecessores, .tem_ciclo_negativo = tem_ciclo_negativo, .allocator = allocator, }; } ``` A função valida a origem e os índices das arestas antes de acessar os slices. Ela também evita somar um peso ao valor sentinela `INF` e usa uma soma verificada para não transformar overflow em uma distância aparentemente válida. O `errdefer` libera alocações já realizadas se uma etapa posterior falhar. Esse padrão é importante em Zig: a função não depende de garbage collector e precisa manter a propriedade dos recursos explícita em todos os caminhos de erro. Para revisar esse fundamento, veja o guia de [gerenciamento de memória em Zig](/tutoriais/gerenciamento-de-memoria-zig/). ## Reconstruindo o caminho mínimo As distâncias respondem “quanto custa?”, mas muitas aplicações também precisam saber “por onde passar?”. O slice `predecessores` registra o vértice anterior sempre que uma distância melhora. ```zig pub fn reconstruirCaminho( allocator: Allocator, predecessores: []const ?usize, origem: usize, destino: usize, ) !?[]usize { if (origem >= predecessores.len or destino >= predecessores.len) { return error.VerticeInvalido; } var reverso = std.ArrayList(usize).init(allocator); errdefer reverso.deinit(); var atual = destino; var passos: usize = 0; while (true) { try reverso.append(atual); if (atual == origem) break; atual = predecessores[atual] orelse return null; passos += 1; if (passos >= predecessores.len) { return error.CadeiaDePredecessoresInvalida; } } std.mem.reverse(usize, reverso.items); return try reverso.toOwnedSlice(); } ``` O limite de passos evita um loop infinito caso a função receba uma cadeia de predecessores inconsistente. Em uso normal, reconstrua caminhos apenas depois de confirmar que `tem_ciclo_negativo` é falso ou depois de identificar precisamente quais vértices não foram afetados pelo ciclo. Um vértice inalcançável permanece com distância `INF` e predecessor `null`. Nesse caso, a função retorna `null`, distinguindo “não existe rota” de uma falha de alocação ou de um índice inválido. ## Detectando um ciclo negativo Considere: ```text 0 → 1 peso 2 1 → 2 peso -4 2 → 1 peso 1 ``` O ciclo `1 → 2 → 1` custa `-3`. Cada volta reduz o custo total em três unidades. Não existe resposta mínima finita para `1`, `2` e para qualquer vértice alcançável a partir deles. A implementação básica informa apenas que existe algum ciclo negativo alcançável. Em uma aplicação mais avançada, você pode descobrir os vértices afetados assim: 1. execute as `V - 1` rodadas normais; 2. na rodada adicional, marque todo destino que ainda puder ser relaxado; 3. percorra o grafo a partir dos vértices marcados; 4. classifique todos os alcançáveis como afetados pelo ciclo. Essa distinção é útil porque um ciclo negativo desconectado da origem não altera o resultado daquela consulta. Da mesma forma, um vértice alcançável pela origem, mas sem rota a partir do ciclo, pode continuar com distância válida. ## Testando a implementação Algoritmos de grafos precisam de testes pequenos e direcionados. Um caso básico pode verificar pesos negativos sem ciclo: ```zig test "bellman-ford calcula pesos negativos sem ciclo" { const allocator = std.testing.allocator; const arestas = [_]Aresta{ .{ .origem = 0, .destino = 1, .peso = 4 }, .{ .origem = 0, .destino = 2, .peso = 5 }, .{ .origem = 1, .destino = 2, .peso = -2 }, .{ .origem = 2, .destino = 3, .peso = 3 }, }; var resultado = try bellmanFord(allocator, 4, &arestas, 0); defer resultado.deinit(); try std.testing.expectEqual(false, resultado.tem_ciclo_negativo); try std.testing.expectEqual(@as(i64, 0), resultado.distancias[0]); try std.testing.expectEqual(@as(i64, 4), resultado.distancias[1]); try std.testing.expectEqual(@as(i64, 2), resultado.distancias[2]); try std.testing.expectEqual(@as(i64, 5), resultado.distancias[3]); } test "bellman-ford detecta ciclo negativo alcancavel" { const allocator = std.testing.allocator; const arestas = [_]Aresta{ .{ .origem = 0, .destino = 1, .peso = 2 }, .{ .origem = 1, .destino = 2, .peso = -4 }, .{ .origem = 2, .destino = 1, .peso = 1 }, }; var resultado = try bellmanFord(allocator, 3, &arestas, 0); defer resultado.deinit(); try std.testing.expect(resultado.tem_ciclo_negativo); } ``` Inclua também testes para grafo vazio, origem inválida, vértice isolado, aresta inválida, overflow, múltiplas arestas entre o mesmo par e ciclo negativo desconectado. O uso de `std.testing.allocator` ajuda a encontrar vazamentos nas rotas exercitadas pelos testes. O [guia de testes em Zig](/artigos/zig-testes-guia-completo/) apresenta outros padrões para organizar casos e falhas. ## Bellman-Ford vs Dijkstra vs Floyd-Warshall | Algoritmo | Objetivo | Pesos negativos | Ciclo negativo | Complexidade típica | |---|---|---:|---:|---:| | Bellman-Ford | uma origem para todos | sim | detecta | O(V × E) | | Dijkstra | uma origem para todos | não | não | O((V + E) log V) | | Floyd-Warshall | todos os pares | sim | detecta | O(V³) | | BFS | uma origem, peso uniforme | não se aplica | não | O(V + E) | Não escolha apenas pelo nome mais conhecido. Primeiro determine as propriedades do problema: - todas as arestas têm o mesmo custo? Use BFS; - os pesos variam, mas nunca são negativos? Use Dijkstra; - existem pesos negativos? Use Bellman-Ford; - você precisa consultar qualquer par repetidamente e o grafo cabe em uma matriz? Considere Floyd-Warshall. Em grafos enormes, O(V × E) pode ser caro. A interrupção antecipada ajuda em entradas favoráveis, mas não muda o pior caso. Faça benchmark com o formato e a distribuição dos dados reais, não apenas com grafos aleatórios pequenos. ## Armadilhas comuns ### Usar infinito e somar sem verificar Somar um peso a `maxInt(i64)` causa overflow. Pule arestas cuja origem ainda esteja inalcançável e use aritmética verificada para distâncias externas ou não confiáveis. ### Detectar qualquer ciclo negativo do grafo Bellman-Ford, a partir de uma origem, detecta ciclos negativos **alcançáveis por ela**. Um ciclo em outro componente não interfere nessa consulta. ### Apresentar distâncias afetadas como definitivas Um booleano global é suficiente para exercícios, mas sistemas reais podem precisar marcar cada vértice afetado. Não exiba um custo como “menor” quando ele pode diminuir indefinidamente. ### Confundir grafo direcionado e não direcionado Em um grafo não direcionado, uma aresta costuma ser representada por duas entradas. Um único peso negativo não direcionado já forma um ciclo negativo de ida e volta, salvo se o modelo tiver uma semântica especial. ### Esquecer a propriedade dos slices O chamador deve executar `deinit` no resultado e liberar o slice devolvido por `reconstruirCaminho`. Documente essa propriedade na API. ## Quando usar Bellman-Ford na prática Bellman-Ford é uma boa escolha quando: - descontos, créditos ou ganhos são representados por pesos negativos; - regras de conversão podem criar ciclos inconsistentes; - um protocolo de roteamento usa relaxamento distribuído por distância; - a entrada precisa ser auditada para detectar custo negativo indefinido; - clareza e correção importam mais que o menor tempo assintótico possível. Para aprender outros percursos fundamentais, veja a implementação de [DFS em Zig](/algoritmos/dfs-busca-profundidade/). Se a meta for praticar representação de coleções, allocators e APIs genéricas antes de avançar em grafos, consulte [estruturas de dados em Zig](/estruturas-dados/). ## Conclusão Bellman-Ford troca desempenho por uma capacidade importante: trabalhar corretamente com pesos negativos e denunciar ciclos que tornam o custo mínimo indefinido. A implementação idiomática em Zig deve validar índices, controlar overflow, explicitar a propriedade da memória, interromper cedo quando não houver relaxamentos e separar distância de reconstrução de rota. A regra de decisão é simples: **pesos negativos ou detecção de ciclo negativo apontam para Bellman-Ford; pesos não negativos apontam para Dijkstra**. Com essa fronteira clara e uma suíte de testes cobrindo entradas adversas, o algoritmo se torna uma peça confiável para bibliotecas, exercícios e sistemas de análise de grafos.