O algoritmo de Bellman-Ford resolve o problema do caminho mais curto a partir de uma única fonte em grafos que podem conter arestas com peso negativo — uma limitação que o Dijkstra não suporta. Além disso, o Bellman-Ford é capaz de detectar ciclos negativos (ciclos cuja soma dos pesos das arestas é negativa), situação em que o caminho mais curto não está definido.
Na prática, o Bellman-Ford é usado em protocolos de roteamento de redes (como o RIP — Routing Information Protocol), arbitragem em mercados financeiros (detecção de ciclos negativos em taxas de câmbio), e em qualquer cenário onde arestas com peso negativo são possíveis: bônus, descontos, ganhos de energia em jogos, entre outros.
Como Funciona
O Bellman-Ford funciona pelo princípio de relaxamento de arestas: para cada aresta (u, v, peso), se a distância conhecida até v pode ser melhorada passando por u, atualizamos.
- Inicializa a distância da origem como 0 e todas as outras como infinito.
- Repete V-1 vezes (onde V é o número de vértices):
- Para cada aresta (u, v, peso), tenta relaxar: se
dist[u] + peso < dist[v], atualizadist[v].
- Para cada aresta (u, v, peso), tenta relaxar: se
- Após V-1 iterações, faz uma verificação extra: se alguma aresta ainda pode ser relaxada, existe um ciclo negativo.
Por que V-1 iterações?
O caminho mais curto em um grafo com V vértices tem no máximo V-1 arestas. Na i-ésima iteração, o algoritmo garante que todos os caminhos com até i arestas estão corretos. Após V-1 iterações, todos os caminhos mais curtos estão calculados (se não houver ciclo negativo).
Diagrama Visual — Relaxamento Iterativo
Grafo de exemplo (direcionado, com pesos negativos):
(0)
/ | \
6/ 7| \2
v v v
(1) (2) (3)
| / |
-3| -2/ |4
v v v
(4)<---(5)
1
Arestas: 0->1:6, 0->2:7, 0->3:2, 1->4:-3, 3->5:4, 5->4:1, 3->2:-2
Iteração | Aresta relaxada | dist[0] | dist[1] | dist[2] | dist[3] | dist[4] | dist[5]
---------|-----------------|---------|---------|---------|---------|---------|--------
Init | - | 0 | INF | INF | INF | INF | INF
1 | 0->1 (6) | 0 | 6 | INF | INF | INF | INF
1 | 0->2 (7) | 0 | 6 | 7 | INF | INF | INF
1 | 0->3 (2) | 0 | 6 | 7 | 2 | INF | INF
1 | 1->4 (-3) | 0 | 6 | 7 | 2 | 3 | INF
1 | 3->5 (4) | 0 | 6 | 7 | 2 | 3 | 6
1 | 5->4 (1) | 0 | 6 | 7 | 2 | 3 | 6
1 | 3->2 (-2) | 0 | 6 | 0 | 2 | 3 | 6
2 | 1->4 (-3) | 0 | 6 | 0 | 2 | 3 | 6
2 | 5->4 (1) | 0 | 6 | 0 | 2 | 3 | 6
2 | 3->5 (4) | 0 | 6 | 0 | 2 | 3 | 6
... | (sem mudanças) | 0 | 6 | 0 | 2 | 3 | 6
Resultado: dist = [0, 6, 0, 2, 3, 6]
Note como a aresta 3->2 com peso -2 permite alcançar o vértice 2 com distância 0 (passando por 0->3->2: 2 + (-2) = 0), melhor que o caminho direto 0->2 (distância 7).
Representação do Grafo
Para Bellman-Ford, é conveniente armazenar arestas como uma lista de arestas (origem, destino, peso), pois o algoritmo itera sobre todas as arestas em cada passo.
/// Uma aresta direcionada com peso.
#[derive(Clone)]
struct Aresta {
origem: usize,
destino: usize,
peso: i64, // i64 para suportar pesos negativos
}
/// Cria a lista de arestas do grafo.
fn criar_arestas() -> Vec<Aresta> {
vec![
Aresta { origem: 0, destino: 1, peso: 6 },
Aresta { origem: 0, destino: 2, peso: 7 },
Aresta { origem: 0, destino: 3, peso: 2 },
Aresta { origem: 1, destino: 4, peso: -3 },
Aresta { origem: 3, destino: 5, peso: 4 },
Aresta { origem: 5, destino: 4, peso: 1 },
Aresta { origem: 3, destino: 2, peso: -2 },
]
}
Complexidade
| Caso | Tempo | Espaço |
|---|---|---|
| Melhor | O(E) | O(V) |
| Médio | O(V * E) | O(V) |
| Pior | O(V * E) | O(V) |
Onde V = número de vértices e E = número de arestas.
- Tempo O(V * E): V-1 iterações externas, cada uma examinando todas as E arestas.
- Espaço O(V): armazena o vetor de distâncias e, opcionalmente, o vetor de predecessores.
- Melhor caso O(E): se nenhuma distância é atualizada na primeira iteração (já estão todas corretas ou inalcançáveis), podemos parar cedo.
- Comparado ao Dijkstra O((V+E) log V), o Bellman-Ford é mais lento, mas suporta pesos negativos.
Implementação em Rust
Bellman-Ford Básico
const INF: i64 = i64::MAX;
#[derive(Clone)]
struct Aresta {
origem: usize,
destino: usize,
peso: i64,
}
/// Executa Bellman-Ford a partir de `origem`.
/// Retorna Ok(distâncias) ou Err se houver ciclo negativo.
fn bellman_ford(
num_vertices: usize,
arestas: &[Aresta],
origem: usize,
) -> Result<Vec<i64>, &'static str> {
let mut dist = vec![INF; num_vertices];
dist[origem] = 0;
// V-1 iterações de relaxamento
for _ in 0..num_vertices - 1 {
let mut houve_melhoria = false;
for aresta in arestas {
if dist[aresta.origem] != INF
&& dist[aresta.origem] + aresta.peso < dist[aresta.destino]
{
dist[aresta.destino] = dist[aresta.origem] + aresta.peso;
houve_melhoria = true;
}
}
// Otimização: se nenhuma distância mudou, pode parar
if !houve_melhoria {
break;
}
}
// Verificação de ciclo negativo
for aresta in arestas {
if dist[aresta.origem] != INF
&& dist[aresta.origem] + aresta.peso < dist[aresta.destino]
{
return Err("Ciclo negativo detectado!");
}
}
Ok(dist)
}
fn main() {
let arestas = vec![
Aresta { origem: 0, destino: 1, peso: 6 },
Aresta { origem: 0, destino: 2, peso: 7 },
Aresta { origem: 0, destino: 3, peso: 2 },
Aresta { origem: 1, destino: 4, peso: -3 },
Aresta { origem: 3, destino: 5, peso: 4 },
Aresta { origem: 5, destino: 4, peso: 1 },
Aresta { origem: 3, destino: 2, peso: -2 },
];
match bellman_ford(6, &arestas, 0) {
Ok(dist) => {
for (v, d) in dist.iter().enumerate() {
if *d == INF {
println!("Distância de 0 a {}: inalcançável", v);
} else {
println!("Distância de 0 a {}: {}", v, d);
}
}
}
Err(msg) => println!("{}", msg),
}
// Saída:
// Distância de 0 a 0: 0
// Distância de 0 a 1: 6
// Distância de 0 a 2: 0
// Distância de 0 a 3: 2
// Distância de 0 a 4: 3
// Distância de 0 a 5: 6
}
Bellman-Ford com Reconstrução de Caminho
const INF: i64 = i64::MAX;
#[derive(Clone)]
struct Aresta {
origem: usize,
destino: usize,
peso: i64,
}
/// Bellman-Ford com reconstrução de caminho.
/// Retorna (distâncias, predecessores) ou Err se houver ciclo negativo.
fn bellman_ford_caminho(
num_vertices: usize,
arestas: &[Aresta],
origem: usize,
) -> Result<(Vec<i64>, Vec<Option<usize>>), &'static str> {
let mut dist = vec![INF; num_vertices];
let mut predecessor: Vec<Option<usize>> = vec![None; num_vertices];
dist[origem] = 0;
for _ in 0..num_vertices - 1 {
let mut houve_melhoria = false;
for aresta in arestas {
if dist[aresta.origem] != INF
&& dist[aresta.origem] + aresta.peso < dist[aresta.destino]
{
dist[aresta.destino] = dist[aresta.origem] + aresta.peso;
predecessor[aresta.destino] = Some(aresta.origem);
houve_melhoria = true;
}
}
if !houve_melhoria {
break;
}
}
// Verificação de ciclo negativo
for aresta in arestas {
if dist[aresta.origem] != INF
&& dist[aresta.origem] + aresta.peso < dist[aresta.destino]
{
return Err("Ciclo negativo detectado!");
}
}
Ok((dist, predecessor))
}
/// Reconstrói o caminho da origem ao destino.
fn reconstruir_caminho(
predecessor: &[Option<usize>],
origem: usize,
destino: usize,
) -> Option<Vec<usize>> {
if destino == origem {
return Some(vec![origem]);
}
if predecessor[destino].is_none() {
return None; // Destino inalcançável
}
let mut caminho = Vec::new();
let mut atual = destino;
while atual != origem {
caminho.push(atual);
match predecessor[atual] {
Some(pred) => atual = pred,
None => return None,
}
}
caminho.push(origem);
caminho.reverse();
Some(caminho)
}
fn main() {
let arestas = vec![
Aresta { origem: 0, destino: 1, peso: 6 },
Aresta { origem: 0, destino: 2, peso: 7 },
Aresta { origem: 0, destino: 3, peso: 2 },
Aresta { origem: 1, destino: 4, peso: -3 },
Aresta { origem: 3, destino: 5, peso: 4 },
Aresta { origem: 5, destino: 4, peso: 1 },
Aresta { origem: 3, destino: 2, peso: -2 },
];
match bellman_ford_caminho(6, &arestas, 0) {
Ok((dist, pred)) => {
for destino in 0..6 {
if dist[destino] == INF {
println!("Vértice {}: inalcançável", destino);
} else if let Some(caminho) = reconstruir_caminho(&pred, 0, destino) {
println!(
"Vértice {} (dist={}): {:?}",
destino, dist[destino], caminho
);
}
}
}
Err(msg) => println!("{}", msg),
}
// Saída:
// Vértice 0 (dist=0): [0]
// Vértice 1 (dist=6): [0, 1]
// Vértice 2 (dist=0): [0, 3, 2]
// Vértice 3 (dist=2): [0, 3]
// Vértice 4 (dist=3): [0, 1, 4]
// Vértice 5 (dist=6): [0, 3, 5]
}
Detecção de Ciclo Negativo
const INF: i64 = i64::MAX;
#[derive(Clone)]
struct Aresta {
origem: usize,
destino: usize,
peso: i64,
}
/// Detecta e retorna os vértices afetados por ciclos negativos.
fn encontrar_vertices_ciclo_negativo(
num_vertices: usize,
arestas: &[Aresta],
origem: usize,
) -> Vec<usize> {
let mut dist = vec![INF; num_vertices];
dist[origem] = 0;
// V-1 iterações normais
for _ in 0..num_vertices - 1 {
for aresta in arestas {
if dist[aresta.origem] != INF
&& dist[aresta.origem] + aresta.peso < dist[aresta.destino]
{
dist[aresta.destino] = dist[aresta.origem] + aresta.peso;
}
}
}
// V-ésima iteração: quem ainda relaxa está em ciclo negativo
let mut afetados = Vec::new();
for aresta in arestas {
if dist[aresta.origem] != INF
&& dist[aresta.origem] + aresta.peso < dist[aresta.destino]
{
afetados.push(aresta.destino);
}
}
afetados
}
fn main() {
// Grafo COM ciclo negativo: 1->2 (3), 2->3 (-6), 3->1 (2)
// Ciclo: 1->2->3->1 = 3 + (-6) + 2 = -1 (negativo!)
let arestas = vec![
Aresta { origem: 0, destino: 1, peso: 5 },
Aresta { origem: 1, destino: 2, peso: 3 },
Aresta { origem: 2, destino: 3, peso: -6 },
Aresta { origem: 3, destino: 1, peso: 2 },
Aresta { origem: 3, destino: 4, peso: 1 },
];
let afetados = encontrar_vertices_ciclo_negativo(5, &arestas, 0);
if afetados.is_empty() {
println!("Nenhum ciclo negativo encontrado.");
} else {
println!("Vértices afetados por ciclo negativo: {:?}", afetados);
}
// Saída: Vértices afetados por ciclo negativo: [2, 4]
}
Exemplo de Execução
Detecção de arbitragem em câmbio (ciclo negativo):
Moedas: USD(0), EUR(1), GBP(2), JPY(3)
Taxas de câmbio (como log negativo para usar Bellman-Ford):
USD->EUR: -ln(0.85) = 0.163
EUR->GBP: -ln(0.78) = 0.248
GBP->USD: -ln(1.55) = -0.438
USD->JPY: -ln(110) = -4.700
JPY->USD: -ln(0.009)= 4.711
Ciclo: USD->EUR->GBP->USD
Soma dos pesos: 0.163 + 0.248 + (-0.438) = -0.027 (NEGATIVO!)
Isso significa: 1 USD -> 0.85 EUR -> 0.663 GBP -> 1.028 USD
Lucro de 2.8% por ciclo = oportunidade de arbitragem!
Variações e Otimizações
1. SPFA (Shortest Path Faster Algorithm)
Uma otimização prática do Bellman-Ford que usa uma fila para processar apenas vértices cujas distâncias mudaram. No caso médio, é significativamente mais rápido, mas no pior caso ainda é O(V * E).
2. Bellman-Ford para Grafos com Restrição de K Arestas
Se queremos o caminho mais curto usando no máximo K arestas, executamos apenas K iterações em vez de V-1. Útil para problemas como “voo mais barato com no máximo K escalas”.
3. Detecção de Todos os Ciclos Negativos
Para identificar todos os vértices afetados por ciclos negativos (não apenas os diretamente no ciclo, mas todos alcançáveis a partir dele), executa-se V iterações adicionais propagando a marca de “afetado por ciclo negativo”.
Quando Usar
Use Bellman-Ford quando:
- O grafo tem arestas com peso negativo (descontos, bônus, ganho de energia).
- Precisa detectar ciclos negativos (arbitragem financeira, verificação de consistência).
- O grafo é relativamente pequeno ou o número de arestas é baixo.
- Precisa encontrar caminhos mais curtos com restrição de número de arestas.
- A simplicidade de implementação é mais importante que performance.
Evite Bellman-Ford quando:
- Todas as arestas têm peso não negativo — use Dijkstra, que é mais rápido.
- Precisa de caminhos entre todos os pares — use Floyd-Warshall.
- O grafo é muito grande — O(V * E) pode ser proibitivo.
Comparação com Outros Algoritmos
| Característica | Bellman-Ford | Dijkstra | Floyd-Warshall | BFS |
|---|---|---|---|---|
| Pesos negativos | Sim | Nao | Sim | N/A (sem peso) |
| Detecção ciclo negativo | Sim | Nao | Sim | N/A |
| Complexidade de tempo | O(V * E) | O((V+E) log V) | O(V^3) | O(V + E) |
| Complexidade de espaço | O(V) | O(V + E) | O(V^2) | O(V) |
| Fonte | Única | Única | Todos os pares | Única |
| Implementação | Simples | Moderada | Simples | Simples |
| Grafos esparsos | Bom | Melhor | Ruim | Melhor |
| Grafos densos | Razoável | Razoável | Bom | Bom |
Exercícios Práticos
Arbitragem de câmbio: Dadas N moedas e taxas de câmbio entre elas, determine se é possível lucrar convertendo dinheiro em ciclo (arbitragem). Use o logaritmo negativo das taxas como peso das arestas.
Voo mais barato com K escalas: Dados N aeroportos, M voos com custos e um limite K de escalas, encontre o voo mais barato de uma cidade a outra usando no máximo K conexões.
Verificação de consistência: Um sistema de restrições tem variáveis x1, x2, …, xn com restrições do tipo
xi - xj <= c. Modele como grafo e use Bellman-Ford para verificar se as restrições são satisfazíveis (ou se há ciclo negativo, indicando contradição).Comparação empírica: Implemente Bellman-Ford e Dijkstra para o mesmo grafo (sem pesos negativos) e meça a diferença de tempo de execução para grafos de tamanhos variados.
Veja Também
Vec— Vetor dinâmico — para armazenar arestas e distânciasHashMap— Mapa hash — para representação alternativa do grafoOption— Tipo opcional — para predecessores e resultados opcionaisResult— Tipo resultado — para retornar erro em caso de ciclo negativo- Algoritmo de Dijkstra — alternativa mais rápida para grafos sem pesos negativos
- Algoritmo de Floyd-Warshall — todos os pares de caminhos mínimos
- Busca em Largura (BFS) — caminho mínimo em grafos sem peso