Algoritmo
Dijkstra
UNIVERSIDADE FEDERAL DE CATALÃO - TEORIA DOS GRAFOS
Rafael Bernardes de Jesus
Henrique Jorge de Oliveira
01 Introdução
02 Exemplo
03 Algoritmo
04 Aplicações
05 Conclusão
01 Introdução
Década de 50;
Caminho mais curto de um nó origem até todos os
outros nós do grafo;
Ponderado;
Dijkstra x DFS x Bellman-Ford;
02
Exemplo
02 Exemplo
Vértices A B C D E F G
Distância
Predecessores
02 Exemplo
Vértices A B C D E F G
Distância 0 ∞ ∞ ∞ ∞ ∞ ∞
Predecessores
02 Exemplo
Vértices A B C D E F G
Distância 0 ∞ ∞ ∞ ∞ ∞ ∞
Predecessores
02 Exemplo
Vértices A B C D E F G
Distância 0 ∞ 3 ∞ ∞ 2 ∞
Predecessores A A
02 Exemplo
Vértices A B C D E F G
Distância 0 ∞ 3 ∞ ∞ 2 ∞
Predecessores A A
02 Exemplo
Vértices A B C D E F G
Distância 0 ∞ 3 ∞ ∞ 2 ∞
Predecessores A A
02 Exemplo
Vértices A B C D E F G
Distância 0 8 3 ∞ 5 2 7
Predecessores F A F A F
02 Exemplo
Vértices A B C D E F G
Distância 0 8 3 ∞ 5 2 7
Predecessores F A F A F
02 Exemplo
Vértices A B C D E F G
Distância 0 8 3 ∞ 5 2 7
Predecessores F A F A F
02 Exemplo
Vértices A B C D E F G
Distância 0 8 3 7 4 2 7
Predecessores F A C C A F
02 Exemplo
Vértices A B C D E F G
Distância 0 8 3 7 4 2 7
Predecessores F A C C A F
02 Exemplo
Vértices A B C D E F G
Distância 0 8 3 7 4 2 7
Predecessores F A C C A F
02 Exemplo
Vértices A B C D E F G
Distância 0 6 3 7 4 2 7
Predecessores E A C C A F
02 Exemplo
Vértices A B C D E F G
Distância 0 6 3 7 4 2 7
Predecessores E A C C A F
02 Exemplo
Vértices A B C D E F G
Distância 0 6 3 7 4 2 7
Predecessores E A C C A F
02 Exemplo
Vértices A B C D E F G
Distância 0 6 3 7 4 2 7
Predecessores E A C C A F
03
Algoritmo
03 Algoritmo
Inicialização Exploração dos vizinhos:
1 2
- Define a origem e seu custo - Escolhe o nó com menor custo
como 0 e todos os outros nós atual e o marca como visitado.
com custo infinito (∞). - Atualiza os custos dos nós
- Marca todos os nós como vizinhos se o caminho passando
não visitados. pelo nó atual for menor que o
custo anteriormente registrado.
Repetição
3
- Repete o processo até que
todos os nós tenham sido
visitados.
03 Algoritmo
03 Algoritmo
03 Algoritmo
04
Aplicações
04 Aplicações
Sistemas de navegação Redes de computadores Jogos e Inteligência Planejamento logístico
(GPS) Artificial
Aplicado em Ajuda na otimização
Usado no encontro da Utilizado para
protocolos de de rotas para
rota mais curta entre pathfinding,
roteamento (ex: OSPF) entregas e
dois pontos em permitindo que NPCs
para determinar o planejamento de
mapas, como em escolham o caminho
caminho mais redes de transporte
aplicativos de mais curto em mapas
eficiente para pacotes público.
navegação (Google de jogos.
de dados.
Maps, Waze).
05
Conclusão
05 Conclusão
Solução ótima, se não há pesos negativos;
Ferramenta poderosa e eficaz;
Alta aplicabilidade;
Amplamente utilizado em diversas áreas, com
diversas funcionalidades;
O algoritmo continua sendo um dos pilares da
computação aplicada.
Referências
Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik,
1(1), 269-271.
Cherkassky, B. V., Goldberg, A. V., & Radzik, T. (1996). Shortest paths algorithms: Theory and
experimental evaluation. Mathematical Programming, 73(2), 129-174.
