2ª Reunião do Grupo de
Estudos
Relator: Danilo M Lage
Contestador: João Eduardo Maeda
Edsger Wybe Dijkstra
11 Maio 1930
6 Agosto 2002
Roterdã, Holanda
Nuenen, Holanda
• Cientista da Computação
• Contribuições:
– Algoritmos
– Linguagem de Programação
• ALGOL 60
– Sistema Operacional
• THE
– Processamento Distribuído
Algoritmo de Dijkstra
• Resolução do caminho de menor comprimento
• Descrição dos Problemas:
– 1º Problema:
• Construir a árvore de menor comprimento total entre todos
os nós de um grafo.
– 2º Problema:
• Encontrar o caminho de menor comprimento total entre dois
determinados nós de um grafo.
Resolução
1º Problema
• Considere 5 conjuntos:
– 3 conjuntos de Ramos:
I
II
III
Ramos em ordem de visitação
Ramos em potencial de pertencerem ao I
Ramos ainda não visitados ou rejeitados
– 2 conjuntos de Nós:
A
B
Conjunto de Nós em ordem de visitação
Conjunto de Nós ainda não visitados
Resolução
1º Problema
• Assertiva de Entrada:
– Um nó arbitrário pertencente ao grafo
– Movê-lo de B para A
– Adiciona seus ramos de conexão a II
• 1º Passo:
– Mover o ramo de menor distância de II para I
– Adicionar a A o nó conectado a esse ramo
– Vá para 2º passo
• 2º Passo:
– Considerando os ramos conectados ao nó recém adicionado a A que
liguem a nós pertencentes a B:
• Se o ramo em consideração for maior do que seus correspondentes,
adicione-o a III (descarte-o)
• Caso contrário, adicione-o a II
– Repita o passo 1 se B e II não sejam vazios.
• Resultado:
– O conjunto I possui a árvore requerida
Exemplo
1º Problema
••
1
2
d
6
3
2
c
3
2
–
–
–
–
–
–
Um nó arbitrário pertencente ao grafo
Mover o ramo
Adicionar
os ramos
de menor
a II distância de II
Movê-lo de B para A
para
I 1º Passo se B e II não vazios
Repita
Adiciona
seus ramos de conexão a II
Adicionar a A o nó conectado a esse ramo
A
a
0
b
1
d
2
e
3
c
4
B
a
b
c
d
e
b
a
Assertiva
1º Passo: de Entrada:
2º
1
ee
I
II
III
ab ad be bc
ab ac ad bc be
1 6 2 4 3
ac dc de cb ce cd
6 4 5 7 5 6
Resolução
2º Problema
• Considere 6 conjuntos:
– 3 conjuntos de Ramos:
I
II
III
Ramos em ordem de visitação
Ramos em potencial de pertencerem ao I
Ramos ainda não visitados ou rejeitados
– 3 conjuntos de Nós:
A
B
C
Nós em ordem de visitação
Nós anteriores aos pertencentes a A
Nós ainda não visitados
Resolução
2º Problema
• Assertiva de Entrada:
– Dois nós arbitrários pertencentes ao grafo
– Mover o nó de partida de C para A
• 1º Passo:
– Investigar todos os ramos em III que partam do nó adicionado em A
– Caso o nó de destino não pertença a B, mover o ramo de menor
distância conectando ambos nós para II e o nó de destino para B
– Caso o nó de destino pertença a B e seja de menor distância que seu
correspondente em II, substituí-lo
– Caso a distância do ramo seja maior que seu correspondente, rejeitá-lo
• 2º Passo:
–
–
–
–
Para cada nó em B, investigar seu peso em relação ao nó de partida
Mover o nó com menor distância de B para A
Mover o ramo correspondente a esse nó de II para I
Repetir o passo 1 até que o nó de chegada esteja contido em A
• Resultado:
– O caminho é encontrado seguindo os nós do conjunto A
Exemplo
2º Problema
• Partir de “a” para “e”
1
b
a
2
d
6
3
2
c
3
A
a
b
B
b
1
e
3
C
a
b
2
e
c
d
e
1
ee
I
ab be
II
ab be
1 2
III
ab ac ad bc be
1 6 2 3 2
Artigo Base
• Linguagem matemática, porém, mais próxima da computacional
• Resolução de um gargalo computacional do algoritmo de Dijkstra
• Utilização de árvore de Fibonacci
• Ampla aplicabilidade desse método
Artigo Base
Algoritmo Original
– Mesmo algoritmo já apresentado
– Possui um gargalo!!!
Legenda:
V = conjunto de todos os nós do grafo
S = conjunto dos nós visitados
n = número de nós
s = nó de partida
v = nó vizinho
ui = nó da iteração i
l(.) = peso de um nó (distância acumulada)
Artigo Base
Algoritmo Proposto
Legenda:
l(.) = lista ordenada de pesos dos nós
highiv = posição do maior peso da lista
lowi = posição do menor peso da lista
Artigo Base
Melhoria da Implementação
Artigo Base
Resultados
Experimento 2:
1:
- Nós ligados
-2
1 Ramos
Ramo aleatório
aleatórios
por nó:
i+ji1
i +ji2
ji1
rand[2,3...30]
[2,3...30]
i rand
- Dmax
ji2 =rand
4 [2,3...20]
- Dmax = 6
Legenda:
T = nº associado ao custo
computacional para as
adições e comparações;
Dmax = maior nº de ramos
incidentes em um nó;
n = nº total de nós;
m = nº total de ramos.
PERGUNTAS???
Exemplo
6
5
5
5
3
2
2
6
4
4
3
3
4
5
3
5
3
4
5
4
3
5
5
2
3
4
4 3
3
4
6
3
4
3
3
1
A ciência não estuda ferramentas,
mas o que fazemos e o que descobrimos
com elas.
E. W. Dijkstra