Algoritmo Bellman-Ford - Bellman–Ford algorithm

Algoritmo Bellman-Ford

Aula	Problema de caminho mais curto de fonte única (para gráficos direcionados ponderados)
Estrutura de dados	Gráfico
Desempenho de pior caso	${\ displaystyle \ Theta (| V || E |)}$
Melhor caso de desempenho	${\ displaystyle \ Theta (| E |)}$
Pior caso de complexidade de espaço	${\ displaystyle \ Theta (| V |)}$

O algoritmo Bellman-Ford é um algoritmo que calcula os caminhos mais curtos de um único vértice de origem para todos os outros vértices em um dígrafo ponderado . É mais lento do que o algoritmo de Dijkstra para o mesmo problema, mas mais versátil, pois é capaz de lidar com gráficos nos quais alguns dos pesos das arestas são números negativos. O algoritmo foi proposto pela primeira vez por Alfonso Shimbel ( 1955 ), mas recebeu o nome de Richard Bellman e Lester Ford Jr. , que o publicou em 1958 e 1956 , respectivamente. Edward F. Moore também publicou uma variação do algoritmo em 1959 e, por esse motivo, às vezes também é chamado de algoritmo Bellman-Ford-Moore .

Pesos negativos de aresta são encontrados em várias aplicações de gráficos, daí a utilidade deste algoritmo. Se um gráfico contém um "ciclo negativo" (ou seja, um ciclo cujas bordas somam um valor negativo) que é alcançável a partir da fonte, então não há caminho mais barato : qualquer caminho que tenha um ponto no ciclo negativo pode se tornar mais barato por mais uma caminhada em torno do ciclo negativo. Nesse caso, o algoritmo Bellman-Ford pode detectar e relatar o ciclo negativo.

Algoritmo

Neste gráfico de exemplo, assumindo que A é a origem e as arestas são processadas na pior ordem, da direita para a esquerda, ele requer o | V | −1 ou 4 iterações para as estimativas de distância convergirem. Por outro lado, se as arestas são processadas na melhor ordem, da esquerda para a direita, o algoritmo converge em uma única iteração.

Como o algoritmo de Dijkstra , Bellman-Ford procede por relaxamento , no qual as aproximações da distância correta são substituídas por outras melhores até que finalmente alcancem a solução. Em ambos os algoritmos, a distância aproximada de cada vértice é sempre uma superestimativa da distância real e é substituída pelo mínimo de seu valor antigo e o comprimento de um caminho recém-encontrado. No entanto, o algoritmo de Dijkstra usa uma fila de prioridade para selecionar avidamente o vértice mais próximo que ainda não foi processado e executa esse processo de relaxamento em todas as suas arestas de saída; em contraste, o algoritmo Bellman-Ford simplesmente relaxa todas as arestas e faz isso vezes, onde é o número de vértices no gráfico. Em cada uma dessas repetições, aumenta o número de vértices com distâncias calculadas corretamente, de onde se segue que eventualmente todos os vértices terão suas distâncias corretas. Este método permite que o algoritmo Bellman-Ford seja aplicado a uma classe mais ampla de entradas do que Dijkstra. As respostas intermediárias dependem da ordem das bordas relaxadas, mas a resposta final permanece a mesma. ${\ displaystyle | V | -1}$${\ displaystyle | V |}$

Bellman – Ford é executado no tempo , onde e são o número de vértices e arestas, respectivamente. ${\ displaystyle O (| V | \ cdot | E |)}$ ${\ displaystyle | V |}$${\ displaystyle | E |}$

function BellmanFord(list vertices, list edges, vertex source) is

    // This implementation takes in a graph, represented as
    // lists of vertices (represented as integers [0..n-1]) and edges,
    // and fills two arrays (distance and predecessor) holding
    // the shortest path from the source to each vertex

    distance := list of size n
    predecessor := list of size n

    // Step 1: initialize graph
    for each vertex v in vertices do

        distance[v] := inf             // Initialize the distance to all vertices to infinity
        predecessor[v] := null         // And having a null predecessor
    
    distance[source] := 0              // The distance from the source to itself is, of course, zero

    // Step 2: relax edges repeatedly
    
    repeat |V|−1 times:
         for each edge (u, v) with weight w in edges do
             if distance[u] + w < distance[v] then
                 distance[v] := distance[u] + w
                 predecessor[v] := u

    // Step 3: check for negative-weight cycles
    for each edge (u, v) with weight w in edges do
        if distance[u] + w < distance[v] then
            error "Graph contains a negative-weight cycle"

    return distance, predecessor

Simplificando, o algoritmo inicializa a distância até a fonte em 0 e todos os outros nós em infinito. Então, para todas as arestas, se a distância até o destino puder ser encurtada tomando a aresta, a distância é atualizada para o novo valor inferior. Em cada iteração i em que as arestas são varridas, o algoritmo encontra todos os caminhos mais curtos de no máximo i arestas (e possivelmente alguns caminhos mais longos do que i arestas). Uma vez que o caminho mais longo possível sem um ciclo podem ser bordas, as bordas devem ser varridas vezes para garantir que o caminho mais curto foi encontrado para todos os nós. Uma varredura final de todas as arestas é realizada e se alguma distância for atualizada, então um caminho de arestas de comprimento foi encontrado que só pode ocorrer se houver pelo menos um ciclo negativo no gráfico. ${\ displaystyle | V | -1}$${\ displaystyle | V | -1}$${\ displaystyle | V |}$

Prova de correção

A exatidão do algoritmo pode ser mostrada por indução :

Lemma . Após i repetições para circuito,

• se Distância ( u ) não for infinito, é igual ao comprimento de algum caminho de s até u ; e
• se houver um caminho de s para u com no máximo i arestas, então a Distância (u) é no máximo o comprimento do caminho mais curto de s até u com no máximo i arestas.

Prova . Para o caso base de indução, considere i=0e o momento antes do loop for ser executado pela primeira vez. Então, para o vértice de origem,, source.distance = 0que está correto. Para outros vértices u , , que também está correcto porque não há nenhum caminho de fonte para u com 0 bordas. u.distance = infinity

Para o caso indutivo, primeiro provamos a primeira parte. Considere um momento em que a distância de um vértice é atualizada por v.distance := u.distance + uv.weight. Por suposição indutiva, u.distanceé o comprimento de algum caminho da fonte até u . Então u.distance + uv.weighté o comprimento do caminho da fonte até v que segue o caminho da fonte até u e depois vai para v .

Para a segunda parte, considere um caminho mais curto P (pode haver mais de um) da fonte para v com no máximo i arestas. Seja u o último vértice antes de v neste caminho. Então, a parte do caminho da fonte para u é um caminho mais curto da fonte para u com no máximo i-1 arestas, pois se não fosse, então deve haver algum caminho estritamente mais curto da fonte para u com no máximo i- 1 arestas, e poderíamos então anexar a aresta uv a esse caminho para obter um caminho com no máximo i arestas que seja estritamente mais curto que P - uma contradição. Por suposição indutiva, u.distanceapós i −1 iterações é no máximo o comprimento desse caminho da fonte até u . Portanto, uv.weight + u.distanceé, no máximo, o comprimento de P . Na i- ^ésima iteração, v.distanceé comparado com uv.weight + u.distancee é igual a ele se uv.weight + u.distancefor menor. Portanto, após i iterações, v.distanceé no máximo o comprimento de P , ou seja, o comprimento do caminho mais curto da fonte até v que usa no máximo i arestas.

Se não houver ciclos de peso negativo, então cada caminho mais curto visita cada vértice no máximo uma vez, portanto, na etapa 3, nenhuma outra melhoria pode ser feita. Por outro lado, suponha que nenhuma melhoria possa ser feita. Então, para qualquer ciclo com vértices v [0], ..., v [ k −1],

v[i].distance <= v[i-1 (mod k)].distance + v[i-1 (mod k)]v[i].weight

Somando ao redor do ciclo, v [ i ] .distance ev [ i −1 (mod k )]. Termos de distância cancelam, deixando

0 <= sum from 1 to k of v[i-1 (mod k)]v[i].weight

Ou seja, todo ciclo tem peso não negativo.

Encontrando ciclos negativos

Quando o algoritmo é usado para encontrar caminhos mais curtos, a existência de ciclos negativos é um problema, impedindo o algoritmo de encontrar uma resposta correta. No entanto, uma vez que termina ao encontrar um ciclo negativo, o algoritmo Bellman-Ford pode ser usado para aplicações em que este é o alvo a ser procurado - por exemplo, em técnicas de cancelamento de ciclo em análise de fluxo de rede .

Aplicativos em roteamento

Uma variante distribuída do algoritmo Bellman-Ford é usada em protocolos de roteamento de vetor de distância , por exemplo, o Routing Information Protocol (RIP). O algoritmo é distribuído porque envolve vários nós (roteadores) dentro de um sistema autônomo (AS) , uma coleção de redes IP tipicamente pertencentes a um ISP. Consiste nas seguintes etapas:

1. Cada nó calcula as distâncias entre si e todos os outros nós dentro do AS e armazena essas informações como uma tabela.
2. Cada nó envia sua tabela para todos os nós vizinhos.
3. Quando um nó recebe tabelas de distância de seus vizinhos, ele calcula as rotas mais curtas para todos os outros nós e atualiza sua própria tabela para refletir quaisquer alterações.

As principais desvantagens do algoritmo Bellman-Ford nesta configuração são as seguintes:

• Não se ajusta bem.
• As mudanças na topologia da rede não são refletidas rapidamente, uma vez que as atualizações são distribuídas nó por nó.
• Conte até o infinito se as falhas de link ou nó tornarem um nó inacessível de algum conjunto de outros nós, esses nós podem gastar para sempre aumentar gradualmente suas estimativas da distância até ele e, enquanto isso, pode haver loops de roteamento.

Melhorias

O algoritmo Bellman-Ford pode ser melhorado na prática (embora não no pior caso) pela observação de que, se uma iteração do loop principal do algoritmo terminar sem fazer nenhuma alteração, o algoritmo pode ser encerrado imediatamente, pois as iterações subsequentes serão não faça mais alterações. Com essa condição de término antecipado, o loop principal pode, em alguns casos, usar muito menos do que | V | - 1 iterações, embora o pior caso do algoritmo permaneça inalterado. Todas as melhorias a seguir mantêm a complexidade de tempo do pior caso. ${\ displaystyle O (| V | \ cdot | E |)}$

Uma variação do algoritmo Bellman-Ford conhecido como Shortest Path Faster Algorithm , descrito pela primeira vez por Moore (1959) , reduz o número de etapas de relaxamento que precisam ser realizadas dentro de cada iteração do algoritmo. Se um vértice v tem um valor de distância que não mudou desde a última vez que as arestas de v foram relaxadas, não há necessidade de relaxar as arestas de v uma segunda vez. Desta forma, à medida que o número de vértices com valores de distância corretos aumenta, o número cujas arestas de saída que precisam ser relaxadas a cada iteração diminui, levando a uma economia de fator constante no tempo para gráficos densos .

Yen (1970) descreveu outra melhoria no algoritmo Bellman-Ford. Seu aprimoramento primeiro atribui alguma ordem linear arbitrária em todos os vértices e, em seguida, particiona o conjunto de todas as arestas em dois subconjuntos. O primeiro subconjunto, E _f , contém todas as arestas ( v _i , v _j ) tais que i < j ; o segundo, E _b , contém arestas ( v _i , v _j ) tais que i > j . Cada vértice é visitado na ordem v ₁ , v ₂ , ..., v _{| V |} , relaxando cada aresta de saída desse vértice em E _f . Cada vértice é então visitado na ordem v _{| V |} , v _{| V | −1} , ..., v ₁ , relaxando cada aresta de saída desse vértice em E _b . Cada iteração do loop principal do algoritmo, após a primeira, adiciona pelo menos duas arestas ao conjunto de arestas cujas distâncias relaxadas correspondem às distâncias de caminho mais curtas corretas: uma de E _f e uma de E _b . Essa modificação reduz o número de pior caso de iterações do loop principal do algoritmo de | V | - 1 a . ${\ displaystyle | V | / 2}$

Outra melhoria, por Bannister & Eppstein (2012) , substitui a ordem linear arbitrária dos vértices usada na segunda melhoria do Yen por uma permutação aleatória . Essa mudança torna o pior caso para a melhoria do iene (no qual as arestas de um caminho mais curto estritamente alternam entre os dois subconjuntos E _f e E _b ) muito improvável de acontecer. Com uma ordenação de vértices permutada aleatoriamente, o número esperado de iterações necessárias no loop principal é no máximo . ${\ displaystyle | V | / 3}$

Notas

Referências

Fontes originais

• Shimbel, A. (1955). Estrutura em redes de comunicação . Anais do Simpósio sobre Redes de Informação. New York, New York: Polytechnic Press of the Polytechnic Institute of Brooklyn. pp. 199–203.
• Bellman, Richard (1958). "Em um problema de roteamento" . Quarterly of Applied Mathematics . 16 : 87–90. doi : 10.1090 / qam / 102435 . MR  0102435 .
• Ford, Lester R. Jr. (14 de agosto de 1956). Teoria do Fluxo de Rede . Paper P-923. Santa Monica, Califórnia: RAND Corporation.
• Moore, Edward F. (1959). O caminho mais curto através de um labirinto . Proc. Internat. Simpósio Switching Theory 1957, Parte II. Cambridge, Massachusetts: Harvard Univ. Aperte. pp. 285–292. MR  0114710 .
• Yen, Jin Y. (1970). "Um algoritmo para encontrar as rotas mais curtas de todos os nós de origem para um determinado destino em redes gerais" . Quarterly of Applied Mathematics . 27 (4): 526-530. doi : 10.1090 / qam / 253822 . MR  0253822 .
• Bannister, MJ; Eppstein, D. (2012). Aceleração aleatória do algoritmo Bellman-Ford . Analytic Algorithmics and Combinatorics (ANALCO12), Kyoto, Japão. pp. 41–47. arXiv : 1111.5414 . doi : 10.1137 / 1.9781611973020.6 .

Fontes secundárias

• Bang-Jensen, Jørgen; Gutin, Gregory (2000). "Seção 2.3.4: O algoritmo Bellman-Ford-Moore". Digraphs: Theory, Algorithms and Applications (Primeira edição). ISBN 978-1-84800-997-4.
• Schrijver, Alexander (2005). "Sobre a história da otimização combinatória (até 1960)" (PDF) . Manual de Otimização Discreta . Elsevier: 1–68.
• Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L. Introdução aos Algoritmos . MIT Press e McGraw-Hill., Segunda edição. MIT Press e McGraw-Hill, 2001. ISBN  0-262-03293-7 . Seção 24.1: O algoritmo Bellman-Ford, pp. 588–592. Problema 24-1, pp. 614–615. Terceira edição. MIT Press, 2009. ISBN  978-0-262-53305-8 . Seção 24.1: O algoritmo Bellman-Ford, pp. 651-655.
• Heineman, George T .; Pollice, Gary; Selkow, Stanley (2008). "Capítulo 6: Algoritmos de gráfico". Algoritmos resumidos . O'Reilly Media . pp. 160–164. ISBN 978-0-596-51624-6.
• Kleinberg, Jon ; Tardos, Éva (2006). Projeto de algoritmo . Nova York: Pearson Education, Inc.
• Sedgewick, Robert (2002). "Seção 21.7: Pesos negativos das bordas". Algoritmos em Java (3ª ed.). ISBN 0-201-36121-3. Arquivado do original em 31/05/2008 . Página visitada em 2007-05-28 .