O algoritmo de Bellman–Ford
Alguns problemas de caminho mais curto têm arestas que tornam um caminho mais barato: um reembolso, um troço a descer, uma taxa de câmbio a seu favor. O algoritmo de Dijkstra não consegue lidar com elas. O algoritmo de Bellman–Ford consegue, trocando a astúcia pela paciência.
A ideia
Todos os algoritmos de caminho mais curto assentam num único movimento, relaxar uma aresta: se ir até u e depois pela aresta u → v for mais curto do que o melhor caminho conhecido até v, usa-se esse. O algoritmo de Dijkstra relaxa cada aresta uma vez, numa ordem engenhosa que só funciona quando nenhuma aresta é negativa. O Bellman–Ford não parte desse pressuposto. Relaxa cada aresta, numa ordem fixa qualquer, vezes sem conta, até as distâncias deixarem de mudar.
Passo a passo
Dê à origem a distância 0 e a todos os outros nós infinito. Repita n − 1 vezes, para n nós: percorra cada aresta u → v e relaxe-a se u tiver distância. Pare mais cedo se uma passagem inteira não alterar nada. Depois faça mais uma passagem. Se alguma aresta ainda puder ser relaxada, há um ciclo com total negativo alcançável a partir da origem; caso contrário, cada distância é a mais curta, e os nós guardados dão os caminhos.
Um exemplo
Tome as arestas de sentido único A → B de comprimento 4, A → C 5, B → D 2 e C → B −3, verificadas por essa ordem, a partir de A. A passagem 1 dá B 4, C 5 e D 6, e depois C → B baixa B para 5 − 3 = 2. A passagem 2 baixa D para 2 + 2 = 4. A passagem 3 não altera nada, por isso a resposta é B 2, C 5, D 4. O algoritmo de Dijkstra teria tornado B definitivo em 4 e D em 6, antes de ver a aresta negativa. Junte uma aresta D → C de comprimento −4, e o ciclo C → B → D → C soma −5: cada passagem volta a baixar as distâncias, e a passagem de verificação assinala-o.
Porque é que n − 1 passagens bastam
Um caminho mais curto, quando existe, nunca repete um nó, por isso tem no máximo n − 1 arestas. Relaxar cada aresta numa passagem estende cada caminho mais curto já corretamente conhecido em mais uma aresta, seja qual for a ordem das arestas. Assim, após a passagem k, todos os caminhos mais curtos com até k arestas estão certos, e após n − 1 passagens, todos. A ordem continua a contar para a velocidade: uma boa ordem pode terminar em uma ou duas passagens.
História e utilizações
Alfonso Shimbel descreveu o método em 1955, Lester Ford Jr. em 1956, Edward F. Moore em 1957 e Richard Bellman em 1958; tem o nome de dois deles, Bellman e Ford. As suas passagens podem ser feitas por cada router por conta própria, o que fez dele a base dos protocolos de encaminhamento por vetor de distâncias como o RIP. Em finanças, tomar o logaritmo negativo das taxas de câmbio transforma uma ronda lucrativa de trocas de moeda, uma arbitragem, num ciclo negativo, que o Bellman–Ford consegue encontrar.
Experimente
Abra a aplicação e prima Avançar. Cada aresta tem sentido único, e alguns comprimentos são negativos. Cada passo verifica uma aresta, numa ordem fixa, e os painéis mostram a passagem e quantas distâncias ela alterou. Normalmente, uma passagem depressa deixa de alterar alguma coisa e a pesquisa para mais cedo. Marque Adicionar um ciclo negativo e veja as distâncias descer passagem após passagem, até a passagem de verificação encontrar o ciclo e o desenhar a vermelho.
Perguntas frequentes
Qual é a complexidade temporal do Bellman–Ford?
O(V · E) para V nós e E arestas: até V − 1 passagens, cada uma a verificar todas as arestas. Com a paragem antecipada, é muitas vezes muito mais rápido na prática, e no melhor caso basta uma única passagem.
O que é um ciclo negativo?
Um ciclo cujos comprimentos de aresta somam menos de zero. Percorrê-lo vezes sem conta torna um caminho tão curto quanto se queira, por isso as distâncias mais curtas para todos os nós alcançáveis através dele não estão definidas.
O Bellman–Ford funciona em grafos não dirigidos?
Só se nenhuma aresta for negativa: uma aresta negativa não dirigida pode ser percorrida para lá e para cá, o que é um ciclo negativo de duas arestas. Com arestas não negativas funciona, mas o algoritmo de Dijkstra é mais rápido.
O que é o SPFA?
O Shortest Path Faster Algorithm, uma versão do Bellman–Ford que, com uma fila, só volta a verificar as arestas que saem de nós cuja distância acabou de mudar. É muitas vezes muito mais rápido, embora o seu pior caso seja o mesmo.
Pronto para experimentar?
Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.
Experimentar o Bellman–Ford