Algoritmo de Dijkstra em Tabelas ou Grafos

Prévia do material em texto

Curso de Engenharia de Produção EaD - CEFET/RJ Disciplina: Pesquisa Operacional-II 
Coordenador da Disciplina: Prof. Ormeu Coelho Tutor à Distância: Breno dos Santos de Assis 
Execução do Algoritmo de Dijkstra em Tabelas 
É possível organizar os cálculos do algoritmo de Dijkstra de uma forma mais compacta que 
aquela mostrada na aula 4 deste curso, na qual a memória das operações corresponde à 
execução do pseudocódigo que fora apresentado. O uso de uma tabela para registrar as 
iterações pode tornar as anotações mais sintéticas, facilitando a compreensão. 
Nesta tabela há tantas linhas quanto forem os vértices para os quais já se identificou ao menos 
um caminho, até a iteração corrente. Há ainda três colunas, uma para registrar os “nomes” dos 
vértices, uma para anotar as informações dos caminhos encontrados, e outra para definir o 
status dos vértices (Rotulado ou Não rotulado) ao longo da execução. 
Um caminho para um dado vértice 𝑗 é expresso pelo par ordenado [𝑑(𝑗),𝑝(𝑗)], onde 𝑑(𝑗) é a 
distância através do melhor caminho identificado até a iteração atual, e 𝑝(𝑗) é o predecessor 
imediato de do vértice 𝑗 no caminho de 𝑟 (vértice de origem) até 𝑠 (vértice de destino). 
Em cada iteração, a linha em negrito corresponde ao último vértice rotulado, que será usado 
para se tentar construir novos caminhos até cada um dos vértices ainda não rotulados. A linha 
em vermelho indica o próximo a ser rotulado (ou seja, o k-ésimo vértice mais próximo da 
origem 𝑟). Veja como ficaria a resolução do exemplo 2 da aula 4, que consiste em encontrar 
um caminho mínimo entre 𝑟 = 1 e 𝑠 = 6 na rede abaixo: 
 
 
 
 
 
 
 
Iteração 1 
Nó [d(j),p(j)] Status 
1 [0,-] Rotulado 
2 [0 + 5, 1] = [5,1] Não rotulado 
3 [0 + 4, 1] = [4,1] Não rotulado 
4 [0 + 10, 1] = [10,1] Não rotulado 
Iteração 2 
Nó Rótulo Status 
1 [0,-] Rotulado 
2 [5,1] Não rotulado 
3 [4,1] Rotulado 
4 [10,1] Não rotulado 
5 [4 + 5, 3] = [9,3] Não rotulado 
 
2 
2 
4 
1 
2 
3 
6 
5 
5 
1 
Curso de Engenharia de Produção EaD - CEFET/RJ Disciplina: Pesquisa Operacional-II 
Coordenador da Disciplina: Prof. Ormeu Coelho Tutor à Distância: Breno dos Santos de Assis 
Iteração 3 
Nó Rótulo Status 
1 [0,-] Rotulado 
2 [5,1] Rotulado 
3 [4,1] Rotulado 
4 [5 + 2,2] = [7,2] Não rotulado 
5 [5 + 2, 2] = [7,2] Não rotulado 
No caso de empate para a escolha do próximo rotulado, pode-se escolher qualquer dos 
envolvidos, pois os demais serão escolhidos na próxima iteração. Por manter a uniformidade 
dos cálculos, neste curso se escolherá sempre o vértice de menor índice. Neste caso, isso 
produz a escolha do vértice 4. 
Iteração 4 
Nó Rótulo Status 
1 [0,-] Rotulado 
2 [5,1] Rotulado 
3 [4,1] Rotulado 
4 [7,2] Rotulado 
5 [7 + 1, 4] = [8,4] Não rotulado 
6 [7 + 3, 4] = [10,4] Não rotulado 
Iteração 5 
Nó Rótulo Status 
1 [0,-] Rotulado 
2 [5,1] Rotulado 
3 [4,1] Rotulado 
4 [7,2] Rotulado 
5 [7,2] Rotulado 
6 [7 + 2, 5] = [9,5] Não rotulado 
 
Uma vez que o nó de destino (𝑠 = 6) foi rotulado, o algoritmo para, retornando o caminho 
ótimo {(1,2), (2,5), (5,6)}, de custo igual a 9. 
 
 
 
 
 
 
 
 
 
Curso de Engenharia de Produção EaD - CEFET/RJ Disciplina: Pesquisa Operacional-II 
Coordenador da Disciplina: Prof. Ormeu Coelho Tutor à Distância: Breno dos Santos de Assis 
Execução do Algoritmo de Dijkstra no Grafo 
A memória de cálculo também pode ser registrada no próprio grafo, associando-se a cada 
vértice uma trinca de valores [ d(j) , p(j) , k ], onde 𝑑(𝑗) e 𝑝(𝑗) têm os mesmos significados de 
antes, e k é o número da iteração na qual o caminho em questão foi encontrado. 
 
Iteração 1 
 
 
 
 
 
 
 
 
 
Iteração 2 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
2 
2 
4 
1 
2 
3 
6 
5 
5 
1 [ 0 , 0 , 0 ] 
[ 5 , 1 , 1 ] [ 10 , 2 , 1 ] 
[ 4 , 1 , 1 ] 
2 
2 
4 
1 
2 
3 
6 
5 
5 
1 [ 0 , 0 , 0 ] 
[ 5 , 1 , 1 ] [ 10 , 2 , 1 ] 
[ 4 , 1 , 1 ] [ 9 , 3 , 2 ] 
Curso de Engenharia de Produção EaD - CEFET/RJ Disciplina: Pesquisa Operacional-II 
Coordenador da Disciplina: Prof. Ormeu Coelho Tutor à Distância: Breno dos Santos de Assis 
Iteração 3 
 
 
 
 
 
 
 
 
 
 
 
 
Iteração 4 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
2 
2 
4 
1 
2 
3 
6 
5 
5 
1 
[ 0 , 0 , 0 ] 
[ 5 , 1 , 1 ] [ 10 , 2 , 1 ] 
[ 4 , 1 , 1 ] [ 9 , 3 , 2 ] 
[ 7 , 2 , 3 ] 
[ 7 , 2 , 3 ] 
2 
2 
4 
1 
2 
3 
6 
5 
5 
1 
[ 0 , 0 , 0 ] 
[ 5 , 1 , 1 ] [ 10 , 2 , 1 ] 
[ 4 , 1 , 1 ] [ 9 , 3 , 2 ] 
[ 7 , 2 , 3 ] 
[ 7 , 2 , 3 ] 
[ 10 , 4 , 4 ] 
Curso de Engenharia de Produção EaD - CEFET/RJ Disciplina: Pesquisa Operacional-II 
Coordenador da Disciplina: Prof. Ormeu Coelho Tutor à Distância: Breno dos Santos de Assis 
Iteração 5 
 
 
 
 
 
 
 
 
 
 
 
Uma vez que o nó de destino (𝑠 = 6) foi rotulado, o algoritmo para, retornando o caminho 
ótimo {(1,2), (2,5), (5,6)}, de custo igual a 9. 
2 
2 
4 
1 
2 
3 
6 
5 
5 
1 
[ 0 , 0 , 0 ] 
[ 5 , 1 , 1 ] [ 10 , 2 , 1 ] 
[ 4 , 1 , 1 ] [ 9 , 3 , 2 ] 
[ 7 , 2 , 3 ] 
[ 7 , 2 , 3 ] 
[ 10 , 4 , 4 ] 
[ 9 , 5 , 5 ]