Algoritmo de Bellman-Ford
- Proposto por
- Richard Bellman and Lester R. Ford
- Ano
- 1956
- Tipo
- algorithm
- Família
- Graph Algorithms
Este texto é uma tradução automática e ainda não foi revisado. Ler o original em inglês
O que ele faz?
O Algoritmo de Bellman-Ford, desenvolvido por Richard Bellman e Lester R. Ford na década de 1950, é um algoritmo fundamental para o cálculo de caminhos mais curtos em grafos ponderados que podem conter pesos de aresta negativos.
Diferentemente do algoritmo de Dijkstra, ele lida corretamente com pesos negativos e pode detectar a presença de ciclos de peso negativo.
A intuição por trás do método
O algoritmo funciona relaxando iterativamente as arestas: para cada aresta, ele verifica se passar por essa aresta oferece um caminho mais curto para o destino do que o melhor caminho conhecido atualmente. Repetindo esse processo para todas as arestas V-1 vezes, onde V é o número de vértices, o algoritmo garante encontrar o caminho mais curto mesmo com pesos negativos. A percepção chave é que qualquer caminho mais curto em um grafo com V vértices contém no máximo V-1 arestas; se as distâncias ainda melhorarem após V-1 iterações, um ciclo negativo deve existir.
História
Richard Bellman desenvolveu o algoritmo em 1958 usando princípios de programação dinâmica, enquanto Lester R. Ford descobriu independentemente uma abordagem semelhante para fluxos em redes em 1956. O algoritmo foi posteriormente desenvolvido e aprimorado na década de 1960, com aplicações estendendo-se a roteamento de rede e aplicações econômicas. Variantes modernas incluem o Shortest Path Faster Algorithm (SPFA) e várias otimizações para estruturas de grafos específicas, embora a abordagem básica de Bellman-Ford permaneça uma referência clássica no design de algoritmos.
Quando usar
Aplique o algoritmo de Bellman-Ford ao calcular caminhos mais curtos em grafos com pesos de aresta negativos. É essencial para a detecção de arbitragem de moeda, protocolos de rede onde os pesos podem ser negativos e qualquer aplicação onde custos ou pesos negativos sejam significativos. Use o algoritmo de Dijkstra se todos os pesos forem não negativos, pois ele é mais eficiente. Para detectar ciclos negativos sem calcular caminhos, este algoritmo também é apropriado.
Limitações e considerações
- Mais lento que Dijkstra para pesos não negativos: O(VE) versus O((V+E)logV)
- Menos eficiente para grafos esparsos em comparação com outros algoritmos
- Requer que todas as arestas sejam listadas explicitamente, tornando-o menos adequado para grafos implícitos ou dinâmicos
- Nenhuma orientação heurística disponível para acelerar o cálculo
As condições da fonte não substituem a revisão científica independente nem a validação por um motor de análise.
Pontos fortes
- Lida corretamente com grafos com pesos de aresta negativos
- Detecta ciclos de peso negativo, prevenindo resultados errôneos de caminhos mais curtos
- Mais simples de entender e implementar do que alguns algoritmos avançados de caminhos mais curtos
- Garantido para encontrar caminhos mais curtos em tempo O(VE)
- Funciona em grafos direcionados e não direcionados (com cautela em não direcionados)
Aplicações
- Detecção de arbitragem de moeda: identificação de ciclos lucrativos em grafos de taxas de câmbio
- Protocolos de roteamento de rede: cálculo de caminhos mais curtos onde os custos de link podem variar ou ser negativos
- Teoria dos jogos: resolução de problemas de caminhos mais curtos com arestas de penalidade ou fatores de desconto
- Robótica: planejamento de caminhos em ambientes com forças repulsivas (pesos negativos)
- Despacho econômico: otimização da geração de energia com funções de custo incluindo termos negativos
- Telecomunicações: encontrar rotas ótimas quando os pesos dos links representam métricas de atraso ou qualidade
Como funciona
Como funciona
Defina a distância para a origem como zero e todas as outras distâncias como infinito; opcionalmente, defina todos os predecessores como nulo.
Repita V-1 vezes: para cada aresta (u, v) com peso w, se distance[u] + w for menor que distance[v], atualize distance[v] e o predecessor de v.
Verifique todas as arestas mais uma vez; se alguma distância melhorar, um ciclo de peso negativo existe. Retorne erro ou identifique o ciclo conforme apropriado.
Erros comuns
- Esquecer de realizar a iteração adicional para detectar ciclos negativos
- Assumir que o algoritmo funciona corretamente em grafos não direcionados com arestas negativas (pode criar ciclos negativos virtuais)
- Usar o algoritmo quando Dijkstra é suficiente, resultando em perda de desempenho desnecessária
Perguntas frequentes
Por que o algoritmo precisa de exatamente V-1 iterações?
Qualquer caminho em um grafo com V vértices tem no máximo V-1 arestas. Ao iterar V-1 vezes, o algoritmo permite que as informações de distância se propaguem por todo o grafo. Uma V-ésima iteração só melhorará as distâncias se um ciclo negativo existir.
Como o algoritmo pode detectar ciclos negativos?
Após completar V-1 iterações, execute mais uma passagem de relaxamento. Se alguma distância diminuir, um ciclo negativo existe. Os nós envolvidos no ciclo podem ser identificados por backtracking usando ponteiros de predecessor.
Qual é a complexidade de tempo e como ela se compara à de Dijkstra?
Bellman-Ford executa em tempo O(VE), onde V são vértices e E são arestas. Dijkstra executa em O((V+E)logV) com um heap binário. Bellman-Ford é mais lento, mas lida com pesos negativos; Dijkstra é mais rápido, mas requer pesos não negativos.
O Bellman-Ford pode funcionar em grafos não direcionados com pesos negativos?
Tecnicamente sim, mas pode criar ciclos negativos espúrios devido à natureza bidirecional das arestas. Cuidados especiais são necessários para interpretar os resultados corretamente. Para grafos não direcionados, considere abordagens alternativas.
Métodos relacionados
Fontes
Bellman, R. (1958). On a routing problem. Quarterly of Applied Mathematics, 16(1), 87-90.
Abrir referência DOICopiado.Ford, L. R. (1956). Network Flow Theory. RAND Corporation Paper P-923.
Abrir referência da publicaçãoCopiado.