08 bellman ford

Prévia do material em texto

Otimização em Redes
Allexandre Fortes S. Reis
Coordenadoria de Engenharia de Produção
Departamento de Engenharia Mecânica
Campus Santo Antônio
Universidade Federal de São João Del Rei
2 de outubro de 2017
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 2 de outubro de 2017 1 / 24
Conteúdo
1
Algoritmo de Bellman-Ford
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 2 de outubro de 2017 2 / 24
Algoritmo de Ford-Moore-Bellman
Quem é(são) o(s) autor(es)?
Há registros históricos de que este algoritmo foi proposto por Shimble em
1955;
Alguns autores denominam o algoritmo de Ford-Moore-Bellman, em home-
nagem a outros três autores que propuseram o mesmo algoritmo em anos
diferentes:
Lester Ford (1956);
Edward Moore (1957);
Richard Bellman (1958).
Comumente chamado de Algoritmo de Bellman-Ford
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 2 de outubro de 2017 3 / 24
Algoritmo de Bellman-Ford
Princípio
Ao invés de fechar um vértice por iteração, como o algoritmo de Dijkstra, exa-
mina todos os vértices de um grafo orientado por iteração até que atualizações
não sejam possíveis;
Dessa forma, trabalha com Rotulamento Modificado;
Determina o menor caminho entre um vértice de origem e todos os demais
vértices do grafo;
Com esta estratégia, é possível calcular caminhos mínimos em grafos com
arestas de peso negativo;
Assim como o algoritmo de Dijkstra, baseia-se no princípio de relaxação: uma
aproximação da distância da origem até cada vértice é gradualmente atuali-
zada por valores mais precisos até que a solução ótima seja atingida.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 2 de outubro de 2017 4 / 24
Algoritmo de Bellman-Ford
Princípio
�Um caminho de i para j com k+1 arestas pode ser obtido a partir de
um caminho de i para j com k arestas�;
Se, em alguma iteração do algoritmo os rótulos dos vértices permane-
cerem inalterados, não haverá atualizações nas próximas iterações e o
algoritmo pode terminar;
Entretanto, se houver atualizações na última iteração do algoritmo, é
sinal de que há pelo menos um ciclo negativo no grafo.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 2 de outubro de 2017 5 / 24
Algoritmo de Bellman-Ford
Terminologia
N(i): Conjunto de vértices antecessores do vértice atual i;
d(i): Vetor que armazena a distância entre o vértice de origem e o vértice i;
p(i): Vetor que armazena o índice do vértice anterior ao vértice i, no caminho
cuja distância está armazenada em d(i);
altera: variável booleana que indica se houve alguma atualização na iteração
atual.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 2 de outubro de 2017 6 / 24
Algoritmo de Bellman-Ford
Entrada: Grafo G = (V,E), matriz de distâncias D = [dij ], ∀(i, j) ∈ E, origem o = 0
1 p(o)← o;
2 para i← 1 até n faça
3 se ∃(o, i) então
4 d(i)← doi;
5 p(i)← o;
6 senão
7 d(i)←∞;
8 p(i)← ∅;
9 fim
10 fim
11 para k ← 1 até n− 1 faça
12 altera ← falso;
13 para i← 1 até n faça
14 para j ∈ N(i) faça
15 se d(i) > d(j) + dji então
16 d(i)← d(j) + dji;
17 p(i)← j;
18 altera ← verdadeiro; //indica que houve alteração
19 fim
20 fim
21 fim
22 se altera = falso então
23 k ← n
24 fim
25 fim
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 2 de outubro de 2017 7 / 24
Algoritmo de Bellman-Ford
Detecção de Ciclos de Custo Negativo
Em caminhos sem ciclos, o caminho mais longo consiste em n− 1
arestas, ou iterações no laço principal do algoritmo;
Se na n-ésima iteração do algoritmo alguma atualização de distâncias
for feita é detectado o ciclo.
Exemplo de ciclo negativo entre os vértices 4 e 5.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 2 de outubro de 2017 8 / 24
Algoritmo de Bellman-Ford
Detecção de Ciclos de Custo Negativo
Em caminhos sem ciclos, o caminho mais longo consiste em n− 1
arestas, ou iterações no laço principal do algoritmo;
Se na n-ésima iteração do algoritmo alguma atualização de distâncias
for feita é detectado o ciclo.
Exemplo de ciclo negativo entre os vértices 4 e 5.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 2 de outubro de 2017 8 / 24
Exemplo
Grafo G. O vértice origem será `1 '.
nó 2 3 4 5 6
p() - - - - -
d() - - - - -
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 2 de outubro de 2017 9 / 24
Exemplo
Vetores após a inicialização do algoritmo.
nó 2 3 4 5 6
p() 1 1 ∅ ∅ ∅
d() 1 3 ∞ ∞ ∞
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 2 de outubro de 2017 10 / 24
Exemplo
k = 1
i = 2, N = {1}
j = 1, d(1) + d12 = 1
nó 2 3 4 5 6
p() 1 1 ∅ ∅ ∅
d() 1 3 ∞ ∞ ∞
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 2 de outubro de 2017 11 / 24
Exemplo
k = 1
i = 3, N = {1, 2}
j = 1, d(1) + d13 = 3
j = 2, d(2) + d23 = 2
nó 2 3 4 5 6
p() 1 2 ∅ ∅ ∅
d() 1 2 ∞ ∞ ∞
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 2 de outubro de 2017 12 / 24
Exemplo
k = 1
i = 4, N = {2, 3, 5}
j = 2, d(2) + d24 = 4
j = 3, d(3) + d34 = 4
j = 5, d(5) + d54 =∞
nó 2 3 4 5 6
p() 1 2 2 ∅ ∅
d() 1 2 4 ∞ ∞
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 2 de outubro de 2017 13 / 24
Exemplo
k = 1
i = 5, N = {2, 6}
j = 2, d(2) + d25 = 3
j = 6, d(6) + d65 =∞
nó 2 3 4 5 6
p() 1 2 2 2 ∅
d() 1 2 4 3 ∞
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 2 de outubro de 2017 14 / 24
Exemplo
k = 1
i = 6, N = {4}
j = 4, d(4) + d46 = 6
nó 2 3 4 5 6
p() 1 2 2 2 4
d() 1 2 4 3 6
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 2 de outubro de 2017 15 / 24
Exemplo
k = 2
i = 2, N = {1}
j = 1, d(1) + d12 = 1
nó 2 3 4 5 6
p() 1 2 2 2 4
d() 1 2 4 3 6
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 2 de outubro de 2017 16 / 24
Exemplo
k = 2
i = 3, N = {1, 2}
j = 1, d(1) + d13 = 3
j = 2, d(2) + d23 = 2
nó 2 3 4 5 6
p() 1 2 2 2 4
d() 1 2 4 3 6
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 2 de outubro de 2017 17 / 24
Exemplo
k = 2
i = 4, N = {2, 3, 5}
j = 2, d(2) + d24 = 4
j = 3, d(3) + d34 = 4
j = 5, d(5) + d54 = 0
nó 2 3 4 5 6
p() 1 2 5 2 4
d() 1 2 0 3 6
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 2 de outubro de 2017 18 / 24
Exemplo
k = 2
i = 5, N = {2, 6}
j = 2, d(2) + d25 = 3
j = 6, d(6) + d65 = 9
nó 2 3 4 5 6
p() 1 2 5 2 4
d() 1 2 0 3 6
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 2 de outubro de 2017 19 / 24
Exemplo
k = 2
i = 6, N = {4}
j = 4, d(4) + d46 = 2
nó 2 3 4 5 6
p() 1 2 5 2 4
d() 1 2 0 3 2
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 2 de outubro de 2017 20 / 24
Exemplo
k = 3
Não há alterações, chega-se ao fim do algoritmo
nó 2 3 4 5 6
p() 1 2 5 2 4
d() 1 2 0 3 2
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 2 de outubro de 2017 21 / 24
Exercício
Execute o Algoritmo de Bellman-Ford no grafo abaixo.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 2 de outubro de 2017 22 / 24
Dúvidas? Valar joll	oris
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 2 de outubro de 2017 23 / 24
Referências
(1) Notas de aula Professor Dr. Marco Antônio Carvalho (DECOM/UFOP);
(2) Notas de aula Professor Dr. Gustavo Peixoto (DECOM/UFOP);
(3) Goldbarg, Marco e Goldbarg, Elizabeth. Grafos: Conceitos, algoritmos e apli-
cações (2012);
(4) Taha, Hamdy. Pesquisa Operacional (2008);
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 2 de outubro de 2017 24 / 24
	Algoritmo de Bellman-Ford