Implementação do algoritmo de custo mínimo de Dijkstra em Python para calcular a distância mínima entre cidades

Algoritmo de Dijkstra; Distância;

Nível da Palestra: Iniciante/Básico

O algoritmo de Dijkstra é um dos métodos mais utilizados para calcular o custo mínimo entre os vértices de um grafo com arestas de peso não negativo. O processo é feito da seguinte forma: um vértice do grafo é escolhido para ser a raiz de busca. A partir daí, o algoritmo calcula e retorna a distância mínima de todos os demais vértices até a raiz. O software proposto receberá algumas cidades (vértices) e suas respectivas rotas de acesso (arestas). Serão escolhidas duas cidades: o ponto de partida e o ponto de chegada. A partir daí, será utilizado o método de Dijkstra para calcular a distância mínima entre estas cidades e será informado ao usuário qual a melhor rota para se percorrer. Este software tem por objetivo diminuir os custos e o tempo nas viagens. Além disso, como ele trabalha offline, poderá ser um ótimo auxílio em locais onde não existe acesso à Internet. A próxima etapa de desenvolvimento será criar um banco de dados com as rotas entre as principais cidades brasileiras para que o usuário não precise informá-las ao software, melhorando, assim, sua usabilidade.

Palestrante

Luiz Augusto de Macêdo Morais

Emas - PB

Graduando em Licenciatura Plena em Computação pela Universidade Estadual da Paraíba. Participa do grupo de pesquisa "Genética e Evolução de Plantas do Semi-Árido" e é monitor da disciplina de "Algoritmos e Linguagens de Programação I - Python". Participou da I Mostra de Iniciação Científica e Extensão da UEPB, na oficina de Interface de Software. 2009. (Oficina) e da II Mostra de Iniciação Científica e Extensão da UEPB (2010).

Voltar para Programação