Otimizador de rotas

Implementação do algoritmo de custo mínimo de Dijkstra em

Python para calcular a distância mínima entre cidades

Luiz Augusto de Macêdo Morais

luizaugustomm@[Link]
Quem sou eu
✔ 18 anos;
✔ Graduando em Licenciatura em Computação – UEPB;
✔ Monitor da disciplina de Linguagem de Programação I
– Python;
✔ Faz parte do grupo de pesquisa “Genética e Evolução
de Plantas do Semiárido” e utiliza o Python na
pesquisa;
✔ Conheceu a linguagem Python há um ano.
Roteiro
● Objetivos
● Quem foi Dijkstra?
● O algoritmo de Dijkstra
● Afinal, pra que serve este algoritmo?
● Implementação do algoritmo em Python
● O otimizador de rotas
● Dúvidas
Roteiro
● Objetivos
● Quem foi Dijkstra?
● O algoritmo de Dijkstra
● Afinal, pra que serve este algoritmo?
● Implementação do algoritmo em Python
● O otimizador de rotas
● Dúvidas
Objetivos
✔ Mostrar quem foi Dijkstra
✔ Explicar o funcionamento do algoritmo de Dijkstra
✔ Exibir um exemplo prático do algoritmo, utilizando a
linguagem Python
✔ Explicar qual é a proposta do programa Otimizador de
rotas
✔ Expor as futuras funcionalidades do software
Roteiro
● Objetivos
● Quem foi Dijkstra?
● O algoritmo de Dijkstra
● Afinal, pra que serve este algoritmo?
● Implementação do algoritmo em Python
● O otimizador de rotas
● Dúvidas
Quem foi Dijkstra?
● Matemático e cientista da computação
● Áreas de atuação:
● Algoritmos;
● Linguagens de programação;
● Sistemas operacionais, etc.
● Criou o primeiro compilador para a
linguagem ALGOL 60
● Foi contrário ao comando GOTO
Edsger Wybe Dijkstra
● A Case against the GO TO Statement (1968) (1930 - 2002)
● Criador do algoritmo do caminho mais
curto (shortest path)
Quem foi Dijkstra?
Prêmios e titulações:
● Membro da Sociedade Britânica de
Computação (1971)
● Prêmio Turing (1972)
● Prêmio AFIPS Harry Goode (1974)
● Prêmio de pioneiro da computação do
IEEE (1982)
● Prêmio ACM SIGCSE para Edsger Wybe Dijkstra
contribuições proeminentes à (1930 - 2002)
instrução da ciência da computação
(1989)
Roteiro
● Objetivos
● Quem foi Dijkstra?
● O algoritmo de Dijkstra
● Afinal, pra que serve este algoritmo?
● Implementação do algoritmo em Python
● O otimizador de rotas
● Dúvidas
O algoritmo de Dijkstra
Características:
● Encontra o menor caminho entre dois
vértices de um grafo
● Não funciona com arestas de peso
negativo. Para isso, usa-se o algoritmo de
Bellman-Ford
● Complexidade O(|V|²)
● O(|E| + |V| * log|V|) (heap de Fibonacci)
O algoritmo de Dijkstra
Pseudocódigo:
# Inicia-se os valores
para todo v ∈ V[G]
dist[v]← ∞
prec[v] ← nulo
dist[s] ← 0

Q ← V[G] # Conjunto dos vértices abertos

S ← ø # Conjunto dos vértices fechados

# Relaxamento das arestas

enquanto Q ≠ ø
u ← extraia-mín(Q)
S ← S ∪ {u}
para cada v adjacente a u
se dist[v] > dist[u] + w(u, v)
então dist[v] ← dist[u] + w(u, v)
prec[v] ← u
O algoritmo de Dijkstra

Execução: B C
1
- Atribui um custo infinito a todas as distâncias, ∞ ∞
exceto a distância do vértice A, que é 0.
10
A
2 3 9 4 6
0

7
Vértices A B C D E 5
Estimativas 0 ∞ ∞ ∞ ∞ ∞ 2 ∞
Precedentes - - - - -
D E
O algoritmo de Dijkstra

Execução: B C
1
- Seleciona A (vértice aberto de menor estimativa); ∞ ∞
- Fecha A;
10
A
2 3 9 4 6
0

7
Vértices A B C D E 5
Estimativas 0 ∞ ∞ ∞ ∞ ∞ 2 ∞
Precedentes A - - - -
D E
O algoritmo de Dijkstra

Execução: B C
1
- Seleciona A (vértice aberto de menor estimativa); 10 ∞
- Fecha A;
10
- Recalcula as estimativas de B e D. A
2 3 9 4 6
0

7
Vértices A B C D E 5
Estimativas 0 10 ∞ 5 ∞ 5 2 ∞
Precedentes A A - A -
D E
O algoritmo de Dijkstra

Execução: B C
1
- Seleciona D (vértice aberto de menor estimativa); 10 ∞
- Fecha D;
10
A
2 3 9 4 6
0

7
Vértices A B C D E 5
Estimativas 0 10 ∞ 5 ∞ 5 2 ∞
Precedentes A A - A -
D E
O algoritmo de Dijkstra

Execução: B C
8 1 14
- Seleciona D (vértice aberto de menor estimativa);
- Fecha D;
10
- Recalcula as estimativas de B, C e E. A
2 3 9 4 6
0

7
Vértices A B C D E 5
Estimativas 0 8 14 5 7 5 2 7
Precedentes A D D A D
D E
O algoritmo de Dijkstra

Execução: B C
8 1 14
- Seleciona E (vértice aberto de menor estimativa);
- Fecha E;
10
A
2 3 9 4 6
0

7
Vértices A B C D E 5
Estimativas 0 8 14 5 7 5 2 7
Precedentes A D D A D
D E
O algoritmo de Dijkstra

Execução: B C
8 1 13
- Seleciona E (vértice aberto de menor estimativa);
- Fecha E;
10
- Recalcula a estimativa de C. A
2 3 9 4 6
0

7
Vértices A B C D E 5
Estimativas 0 8 13 5 7 5 2 7
Precedentes A D E A D
D E
O algoritmo de Dijkstra

Execução: B C
8 1 13
- Seleciona B (vértice aberto de menor estimativa);
- Fecha B;
10
A
2 3 9 4 6
0

7
Vértices A B C D E 5
Estimativas 0 8 13 5 7 5 2 7
Precedentes A D E A D
D E
O algoritmo de Dijkstra

Execução: B C
8 1 9
- Seleciona B (vértice aberto de menor estimativa);
- Fecha B;
10
- Recalcula a estimativa de C. A
2 3 9 4 6
0

7
Vértices A B C D E 5
Estimativas 0 8 9 5 7 5 2 7
Precedentes A D B A D
D E
O algoritmo de Dijkstra

Execução: B C
8 1 9
- Seleciona C (vértice aberto de menor estimativa);
- Fecha C
10
A
2 3 9 4 6
0

7
Vértices A B C D E 5
Estimativas 0 8 9 5 7 5 2 7
Precedentes A D B A D
D E
Roteiro
● Objetivos
● Quem foi Dijkstra?
● O algoritmo de Dijkstra
● Afinal, pra que serve este algoritmo?
● Implementação do algoritmo em Python
● O otimizador de rotas
● Dúvidas
Afinal, pra que serve este algoritmo?

● Linhas de transmissão elétrica

● Conexão de redes
● Panejamento de movimentos de um robô
● Planejamento de rotas e tempo de viagens
Roteiro
● Objetivos
● Quem foi Dijkstra?
● O algoritmo de Dijkstra
● Afinal, pra que serve este algoritmo?
● Implementação do algoritmo em Python
● O otimizador de rotas
● Dúvidas
Implementação do algoritmo em Python
Roteiro
● Objetivos
● Quem foi Dijkstra?
● O algoritmo de Dijkstra
● Afinal, pra que serve este algoritmo?
● Implementação do algoritmo em Python
● O otimizador de rotas
● Dúvidas
O otimizador de rotas
Características:
● Auxilia em viagens de percursos
desconhecidos;
● Calcula a rota mínima entre cidades;
● Mostra passo a passo o percurso escolhido;
● Informa a distância e o tempo total de viagem;
● Não necessita de conexão com a Internet.
O otimizador de rotas
Screenshots:

Janela principal
O otimizador de rotas
Screenshots:

Resultado simples
O otimizador de rotas
Screenshots:
Resultado completo
O otimizador de rotas
Próximos passos:
● Exibir o mapa da rota escolhida;
● Informar a rota mais rápida;
● Aumentar o número de cidades e Estados;
● Exibir informações sobre pedágios e tipo de
estrada;
● Otimizar o algoritmo.
Roteiro
● Objetivos
● Quem foi Dijkstra?
● O algoritmo de Dijkstra
● Afinal, pra que serve este algoritmo?
● Implementação do algoritmo em Python
● O otimizador de rotas
● Dúvidas
Dúvidas
Obrigado!

Twitter: @luizaugustomm
E-mail: luizaugustomm@[Link]
Site: [Link]
 Referências
Edsger Dijkstra. Disponível em: <[Link]
Acesso em: 8 de outubro de 2010.
Algoritmo de Dijkstra. Disponível em:
<[Link] Acesso em: 8 de outubro de
2010.
Algoritmo de Dijkstra para cálculo do Caminho de Custo Mínimo. Disponível em:
<[Link] Acesso em: 8 de
outubro de 2010.
LEMOS, G. Otimização de Rotas Rodoviárias Utilizando o Algoritmo de Dijkstra
e a API do Google Maps. 2009. 24f. Universidade Estadual de Londrina. Londrina,
Paraná, 2009.
MÉNDEZ, Y. S.; GUARDIA, L. E. T. Problema do caminho mais curto:
Algoritmo de Dijkstra. Universidade Federal Fluminense. Rio de Janeiro, Rio
de Janeiro, 2008.