Skip to content
Voltar aos resultados

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

Tamanho da fonte

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

1

Defina a distância para a origem como zero e todas as outras distâncias como infinito; opcionalmente, defina todos os predecessores como nulo.

2

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.

3

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

  1. Bellman, R. (1958). On a routing problem. Quarterly of Applied Mathematics, 16(1), 87-90.

    Abrir referência DOI
    Copiado.
  2. Ford, L. R. (1956). Network Flow Theory. RAND Corporation Paper P-923.

    Abrir referência da publicação
    Copiado.