Ciência da Computação GRAFOS - Universidade do Sul de SCpaginas.unisul.br/max.pereira/Grafos Aula 07.pdf · Algoritmo de Bellman-Ford Ciência da Computação - GRAFOS Arestas

Ciência da Computação

GRAFOS

Aula 07 Algoritmos de Caminho Mínimo:Bellman-Ford / Floyd-Warshall

Max Pereira

Algoritmo de Bellman-Ford

Ciência da Computação - GRAFOS

Arestas com valores negativos podem parecer inúteis, mas elas podemexplicar uma série de fenômenos, como por exemplo, fluxo de caixa, calorliberado/absorvido em uma reação química, etc.

Arestas com pesos negativos podem criar ciclos negativos, isto é, um cicloque irá reduzir a distância total, retornando ao mesmo ponto.

Algoritmos de caminho mínimo, como o Dijkstra, que não são capazes de detectar tais ciclos podem produzir resultados incorretos.

Ótimo: S A EDijkstra: S B E

Ótimo: S A BDijkstra: S B



Ford, L. R., Network Flow Theory., Santa Monica, Calif.: RAND Corporation, P-923, 1956. As of September 13, 2017: https://www.rand.org/pubs/papers/P923.html



Ao invés de fechar um vértice por iteração, como o algoritmo de Dijkstra, examina todos os vértices de um grafo orientado por iteração até queatualizações não sejam possíveis.

Com esta estratégia é possível calcular caminhos mínimos em grafos com arestas com valores negativos.

Assim como o algoritmo de Dijkstra, baseia-se no princípio de relaxação: umaaproximação da distância da origem até cada vértice é gradualmente atualizadapor valores mais precisos até a que a solução ótima seja atingida.



O que é um ciclo negativo?Um ciclo negativo significa que, se somarmos os pesos de todas as arestas no ciclo, a soma se tornará negativa. O grafo abaixo contém um ciclo negativo (C, H, G, C) com soma igual a -4.



Então, como o algoritmo de Bellman-Ford resolve o problema dos ciclosnegativos?

Na verdade ele não resolve, o algoritmo não consegue responder com um caminho difinitivo. É teoricamente impossível encontrar o caminho mínimo se existir um ciclo negativo. Se tentarmos encontrar o caminho mínimo, retornamos ao ciclo mais de uma vez e o resultado é um caminho menor ainda.Na prática, esse algoritmo ou informará um caminho mínimo válido ou indicaráa existência de um ciclo negativo.



Estratégia:Considerando o vértice A como a origem, adicionamos todos os vertices (A, B, C, D, E, F, G, H) a uma lista. Para todos os vertices, exceto o vértice A, associamosum custo infinito.



A partir da origem (A), avaliamos todas as arestas no grafo (1ª iteração).

(A, E) : E = MIN(E[∞] , A[0] + W{A,E}[6]). (E) = 6.(A, B) : B = MIN(B[∞] , A[0] + W{A,B}[8]). (B) = 8.(B, C) : C = MIN(C[∞] , B[8] + W{B,C}[6]). (C) = 14.(C, H) : H = MIN(H[∞] , C[14] + W{C,H}[4]). (H) = 18.(H, G) : G = MIN(G[∞] , H[18] + W{H,G}[-2]). (G)= 16.(G, C) : C = MIN(C[14] , G[16] + W{G,C}[-1]). (C) = 14.(G, D) : D = MIN(D[∞] , G[16] + W{G,D}[1]). (D) = 17.(D, B) : B = MIN(B[8] , D[17] + W{D,B}[2]). (B) = 8.(E, F) : F = MIN(F[∞] , E[6] + W{E,F}[3]). (F) = 9.(E, G) : G = MIN(G[16] , E[6] + W{E,G}[2]). (G) = 8.(F, G) : G = MIN(G[8] , [9] + W{F,G}[6]). (G) = 8.

O custo para alcançar cada vértice pode ser atualizado Kvezes (onde K é o número de arestas que chegam no vértice).



Avaliamos, novamente, todas as arestas no grafo (2ª iteração).Note que apenas os vértices C, D e G foram atualizados.

(A, E) : E = MIN(E[6] , A[0] + W{A,E}[6]). (E)= 6.(A, B) : B = MIN(B[8] , A[0] + W{A,B}[8]). (B) = 8.(B, C) : C = MIN(C[14] , B[8] + W{B,C}[6]). (C)= 14.(C, H) : H = MIN(H[18] , C[14] + W{C,H}[4]).(H)=18.(H, G) : G = MIN(G[8] , H[18] + W{H,G}[-2]).(G) = 8.(G, C) : C = MIN(C[14] , G[8] + W{G,C}[-1]). (C) = 7.(G, D) : D = MIN(D[17] , G[8] + W{G,D}[1]). (D) = 9.(D, B) : B = MIN(B[8] , D[9] + W{D,B}[2]).(B) = 8.(E, F) : F = MIN(F[9] , E[6] + W{E,F}[3]). (F) = 9.(E, G) : G = MIN(G[8] , E[6] + W{E,G}[2]).(G) = 8.(F, G) : G = MIN(G[8] , F[9] + W{F,G}[6]).(G) = 8



Avaliamos, novamente, todas as arestas no grafo (3ª iteração).Note que apenas o vértice H foi atualizado.

(A, E) : E = MIN(E[6] , A[0] + W{A,E}[6]). (E) = 6.(A, B) : B = MIN(B[8] , A[0] + W{A,B}[8]). (B)= 8.(B, C) : C = MIN(C[7] , B[8] + W{B,C}[6]). (C) = 7.(C, H) : H = MIN(H[18] , C[7] + W{C,H}[4]). (H)= 11.(H, G) : G = MIN(G[8] , H[11] + W{H,G}[-2]). (G)= 8.(G, C) : C = MIN(C[7] , G[8] + W{G,C}[-1]).(C)= 7.(G, D) : D = MIN(D[9] , G[8] + W{G,D}[1]). (D)= 9.(D, B) : B = MIN(B[8] , D[9] + W{D,B}[2]). (B)= 8.(E, F) : F = MIN(F[9] , cost E[6] + W{E,F}[3]). (F)=9.(E, G) : G = MIN(G[8] , E[6] + W{E,G}[2]). (G)= 8.(F, G) : G = MIN(G[8] , F[9] + W{F,G}[6]). (G)=8.



Estratégia:Se continuarmos repetindo o processo (novas iterações) poderemos encontraruma das seguintes situações:

1. Não será efetuada mais nenhuma atualização nas próximas iterações. Nessecaso, encerramos o processo para melhorar a eficiência do algoritmo.

2. As atualizações continuarão sendo efetuadas e repetiremos o processo até|V| -1.

Uma vez encerrada as iterações, precisaremos refazer o processo mais uma vez, para verificar se os custos continuam reduzindo. Se houver ainda redução noscustos, podemos afirmar que existe um ciclo negativo e um caminho mínimonão existe.



Estratégia:O algoritmo trabalha superestimando o comprimento do caminho entre o vértice inicial e todos os outros vértices. Depois, de forma iterativa, reavaliaessas estimativas encontrando novos caminhos que são menores do que osanteriores. Fazendo isso, de forma repetitiva, para todos os vértices, garantimosque o resultado final seja ótimo.

Apesar de ser mais lento que o algoritmo de Dijkstra, ele é capaz de serexecutado em grafos que contenham arestas com valores negativos. É importante notar que se existir um ciclo negativo no grafo, não haverá caminhomínimo. Avaliar o ciclo negativo infinitamente continuará a reduzirr o custo do caminho.



Executar o algoritmo com a seguinte lista de arestas:





Bellman Ford vs DijkstraAs estruturas dos algoritmos de Bellman-Ford e de Dijkstra são muito similares. Enquanto Dijkstra verifica somente os adjacentes imediatos de um vértice, Bellman-Ford passa por cada uma das arestas em todas as iterações.

Algoritmo de Floyd-Warshall


Os algoritmos de Bellman-Ford e Dijkstra encontram o caminho mínimo a partirde uma determinada origem. Porém, podemos querer encontrar os caminhosmínimos entre todos os pares de vértices. Podemos executar os algoritmos para cada vértice no grafo ou utiliza o algoritmo de Floyd-Warshall, que retorna oscaminhos mínimos entre todos os pares de vertices.



Definição:Os vértices v2, v3, …, vl-1 são chamados de vértices intermediários do caminhop = {v1, v2, …,vl}.

Seja 𝑑𝑖𝑗(𝑘)

o comprimento do caminho mínimo de i a j tal que todos os vértices

intermediários no caminho (se houver) estão no conjunto {1, 2, …, k}

𝑑𝑖𝑗(0)

representa a ausência de vértices intermediários e 𝐷𝑘 representa a

matriz n n [𝑑𝑖𝑗(𝑘)

].

Sabendo que 𝑑𝑖𝑗(𝑛)

é a distância entre i e j, então nosso objetivo é calcular 𝐷(𝑛).



Observação:Para o caminho mínimo entre i e j, para qualquer vértice intermediário, no caminho, escolhido no conjunto {1, 2, …, k}, há duas possibilidades:

1. K não é um vértice do caminho: esse caminho tem comprimento 𝑑𝑖𝑗(𝑘−1)

2. K é um vértice do caminho: esse caminho tem comprimento 𝑑𝑖𝑘(𝑘−1)

+ 𝑑𝑘𝑗(𝑘−1)

Vamos considerar um caminho mínimo de i a j que contenha o vértice k, ou seja, um subcaminho de i a k e um subcaminho de k a j.Cada subcaminho pode conter apenas vértices intermediários {1, ..., k-1} e deve

ser o menor possível, ou seja, eles têm comprimentos 𝑑𝑖𝑘(𝑘−1)

e 𝑑𝑘𝑗(𝑘−1)

.

Assim, o caminho tem comprimento 𝑑𝑖𝑘(𝑘−1)


.



Observação:

1. K não é um vértice do caminho: esse caminho tem comprimento 𝑑𝑖𝑗(𝑘−1)

2. K é um vértice do caminho: esse caminho tem comprimento 𝑑𝑖𝑘(𝑘−1)


Combinando os dois casos temos:

𝑑𝑖𝑗(𝑘)

= min{ 𝑑𝑖𝑗(𝑘−1)

, 𝑑𝑖𝑘(𝑘−1)


}.



Procedimento:

𝐷(0) = [𝑤𝑖𝑗], a matriz de pesos (valores).

Calcule 𝐷(𝑘) a partir de 𝐷(𝑘−1) usando

𝑑𝑖𝑗(𝑘)

= min( 𝑑𝑖𝑗(𝑘−1)

, 𝑑𝑖𝑘(𝑘−1)


)

Para k = 1, ..., n.





Exemplo:



Exemplo:

Inicialização: (k = 0)



Exemplo:Iteração 1: (k = 1)As distâncias entre 2 3 e 2 4 são encontradas através do vértice 1.



Exemplo:Iteração 2: (k = 2)As distâncias entre 4 1, 5 1 e 5 3 são encontradas através do vértice 2.



Exemplo:Iteração 3: (k = 3)Nenhuma distância é encontrada passando pelo vértice 3.



Exemplo:Iteração 4: (k = 4)As distâncias entre 1 2, 1 3, 2 3, 3 1, 3 2, 5 1, 5 2, 5 3 e 5 4 são encontradas através do vértice 4.



Exemplo:Iteração 5: (k = 5)Nenhuma distância é encontrada passando pelo vértice 5.



Exemplo:As distâncias finais para todos os pares de vértices são apresentadas na matriz D.



O algoritmo de Floyd-Warshall encontra o caminho mínimo em um grafovalorado com arestas positivas ou negativas (sem ciclos negativos).



Executar o algoritmo:

Documents

Ciência da Computação GRAFOS - Universidade do Sul de SCpaginas.unisul.br/max.pereira/Grafos Aula 07.pdf · Algoritmo de Bellman-Ford Ciência da Computação - GRAFOS Arestas