07 dijkstra

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
14 de setembro de 2017
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 14 de setembro de 2017 1 / 23
Conteúdo
1
Single-source Shortest Path Problem
2
Algoritmo de Dijkstra
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 14 de setembro de 2017 2 / 23
Single-source Shortest Path Problem
Definição
i. Consiste em determinar o menor caminho entre um vértice de origem o e todos
os demais vértices do grafo.
ii. Dado um grafo direcionado G = (V,A) e ponderado, em que w(u, v) denota
o peso do arco (u, v), consiste em determinar o caminho mais curto dv entre
um vértice de origem s e todos os demais vértices v do grafo
iii. Algoritmos: Dijkstra, Bellman-Ford, Busca em Largura (GND), etc.
Modelo
min dv
s.a.:
dv − du ≤ w(u, v) ∀(u, v) ∈ a
ds = 0
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 14 de setembro de 2017 3 / 23
Algoritmo de Dijkstra
Edsger W. Dijkstra
(?) 1930 � (†) 2002
i. 1959 - Algoritmo de Dijkstra para Caminhos Mínimos;
ii. Foi concebido em 20 minutos em um dia em que ele estava cansado em queria percorrer a
menor distância entre dois locais;
iii. Encontra a distância entre determinado nó origem e os demais nós
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 14 de setembro de 2017 4 / 23
Algoritmo de Dijkstra
Princípio
Ideia Básica: partir da origem o e rotular permanentemente os nós na ordem de
suas distâncias d() de o.
1. Inicialização:
I d(o)← 0
I d(i)←∞, ∀i ∈ N \ {o}.
2. Demais iterações:
I
o rótulo de um nó i que é aquele com a menor distância desde a origem por um caminho
cujos nós intermediários são todos rotulados permanentemente.
I
O algoritmo seleciona o nó com o menor rótulo temporário, o rotula como permanente
e pesquisa os arcos que saem de i, atualizando a distância dos seus nós adjacentes.
I
O algoritmo termina quando todos os nós estiverem rotulados permanentemente.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 14 de setembro de 2017 5 / 23
Algoritmo de Dijkstra
Terminologia
1. Classificação:
fechado: caso o caminho mínimo da origem até ele já tenha sido calculado;
aberto: caso contrário.
2. Notação:
a. F : Conjunto de vértices fechados;
b. A: Conjunto de vértices abertos;
c. N : Conjunto de vértices vizinhos ao vértice atual;
d. d[i]: Vetor que armazena a distância entre o vértice de origem e o vértice i;
e. p[i]: Vetor que armazena o índice do vértice predecessor ao vértice i, no caminho
cuja distância está armazenada em d[i];
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 14 de setembro de 2017 6 / 23
Algoritmo de Dijkstra
Terminologia
1. Classificação:
fechado: caso o caminho mínimo da origem até ele já tenha sido calculado;
aberto: caso contrário.
2. Notação:
a. F : Conjunto de vértices fechados;
b. A: Conjunto de vértices abertos;
c. N : Conjunto de vértices vizinhos ao vértice atual;
d. d[i]: Vetor que armazena a distância entre o vértice de origem e o vértice i;
e. p[i]: Vetor que armazena o índice do vértice predecessor ao vértice i, no caminho
cuja distância está armazenada em d[i];
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 14 de setembro de 2017 6 / 23
Algoritmo de Dijkstra
Entrada: Grafo G = (N,E), matriz de distâncias D = [dij ], ∀(i, j) ∈ E, origem o = 0
1 INICIALIZAÇÃO
2 d(o)← 0;
3 p(o)← 0;
4 para todo i ∈ N \ {0} faça
5 d(i)←∞;
6 p(i)← ∅;
7 fim
8 A← N ;
9 F ← ∅;
10 enquanto F 6= N* faça
11 r ← j, tal que minj∈A{d[j]};
12 F ← F ∪ {r};
13 A← A \ {r};
14 V ← V \ F ; //conjunto de nós adjacentes de r
15 para todo i ∈ V faça
16 δ ← min{d[i], (d[r] + dri)};
17 se δ < d[i] então
18 d(i)← δ;
19 p(i)← r;
20 fim
21 fim
22 fim
*A condição de repetição da linha 10 pode ser trocada por A 6= ∅
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 14 de setembro de 2017 7 / 23
Exemplo
Grafo G. O vértice origem será `a'. Deseja-se saber a distância até j
nó a b c d e f g h i j
p() - - - - - - - - - -
d() - - - - - - - - - -
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 14 de setembro de 2017 8 / 23
Exemplo
Rotulação após a inicialização do algoritmo.
O primeiro número é p[i] e o segundo, d[i].
Os vértices de F serão marcados em azul.
nó a b c d e f g h i j
p() a 0 0 0 0 0 0 0 0 0
d() 0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 14 de setembro de 2017 9 / 23
Exemplo
Exame do vértice a.
p[b], d[b], p[c], d[c], p[d] e d[d] são atualizados.
nó a b c d e f g h i j
p() a a a a 0 0 0 0 0 0
d() 0 60 54 42 ∞ ∞ ∞ ∞ ∞ ∞
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 14 de setembro de 2017 10 / 23
Exemplo
Exame do vértice d .
p[e], d[e], p[f ], d[f ], p[g] e d[g] são atualizados.
nó a b c d e f g h i j
p() a a a a d d d 0 0 0
d() 0 60 54 42 68 94 129 ∞ ∞ ∞
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 14 de setembro de 2017 11 / 23
Exemplo
Exame do vértice c.
p[e] e d[e] não são atualizados.
nó a b c d e f g h i j
p() a a a a d d d 0 0 0
d() 0 60 54 42 68 94 129 ∞ ∞ ∞
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 14 de setembro de 2017 12 / 23
Exemplo
Exame do vértice b.
p[f ] e d[f ] são atualizados.
nó a b c d e f g h i j
p() a a a a d b d 0 0 0
d() 0 60 54 42 68 89 129 ∞ ∞ ∞
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 14 de setembro de 2017 13 / 23
Exemplo
Exame do vértice e.
p[i] e d[i] são atualizados.
nó a b c d e f g h i j
p() a a a a d b d 0 e 0
d() 0 60 54 42 68 89 129 ∞ 141 ∞
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 14 de setembro de 2017 14 / 23
Exemplo
Exame do vértice f .
p[g], d[g], p[h] e d[h] são atualizados.
nó a b c d e f g h i j
p() a a a a d b f f e 0
d() 0 60 54 42 68 89 109 114 141 ∞
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 14 de setembro de 2017 15 / 23
Exemplo
Exame do vértice g .
p[j] e d[j] são atualizados.
nó a b c d e f g h i j
p() a a a a d b f f e g
d() 0 60 54 42 68 89 109 114 141 141
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 14 de setembro de 2017 16 / 23
Exemplo
Exame do vértice h.
p[j] e d[j] são atualizados.
nó a b c d e f g h i j
p() a a a a d b f f e h
d() 0 60 54 42 68 89 109 114 141 139
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 14 de setembro de 2017 17 / 23
Exemplo
Exame do vértice j .
Nenhuma atualização.
nó a b c d e f g h i j
p() a a a a d b f f e h
d() 0 60 54 42 68 89 109 114 141 139
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 14 de setembro de 2017 18 / 23
Exemplo
caminho mais curto de a para j .
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 14 de setembro de 2017 19 / 23
Algoritmo de Dijkstra
Principais críticas
i. O algoritmo é incapaz de calcular os caminhos mínimos caso existam
I
Arestas com custo negativo;
I
ciclos.
ii. O algoritmo só calcula os caminhos mínimos a partir de uma única origem;
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 14 de setembro de 2017 20 / 23
Exercício
Execute o Algoritmo de Dijkstra no grafo abaixo.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 14 de setembro de 2017 21 / 23
Dúvidas? Valar joll	oris
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 14 de setembro de 2017 22 / 23
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);
AllexandreFortes S. Reis (UFSJ) Otimização em Redes 14 de setembro de 2017 23 / 23
	Single-source Shortest Path Problem
	Algoritmo de Dijkstra