Algoritmos-e-Estrutura-de-Dados 🧑‍💻

Projeto de Algortimos do curso de Sistemas de Informação UFPE

Objetivo do projeto:

• Utilizar o algoritmo de dijkstra em um contexto real de aplicação

Sobre o problema:

Dentre tantos aeroportos internacionais espalhados pelo mundo, o número de rotas que podem ser feitas entre dois aeroportos é gigantesco. Com o objetivo de otimizar o tempo gasto na tarefa de encontrar esses caminhos, e de conseguir o caminho mais curto possível, decidimos colocar em prática os nossos conhecimentos e desenvolver um algoritmo que resolva esse problema.

Base de dados utilizada:

Com o uso do site www.flightconnections.com anotamos em um arquivo.txt alguns dos aeroportos (93) e suas conexões (135). Cada linha do arquivo segue o seguinte padrão: origem destino distância. Os nomes dos aeroportos estão abreviados pelas iniciais e a distância é dada em milhas. Os aeroportos representam os vértices do grafo, as conexões as arestas e a distância o peso da aresta

Bibliotecas utilizadas

• MatPlotLib
• Networkx
• PySimpleGUI

A Solução:

Para resolver o problema, escolhemos o algoritmo de Dijkstra, por ser simples e não haver arestas de peso negativo no nosso grafo. O algoritmo funciona da seguinte maneira

1. O nó de origem recebe peso de caminho 0, e os demais recebem esse peso como infinito.


2. O algoritmo começa pelo nó de origem e analisa o grafo inteiro em busca do menor caminho. Ele mantém o valor do menor caminho armazenado e o atualiza sempre que encontra um caminho menor.


3. O peso de caminho que um nó recebe é igual ao peso do seu antecessor + peso da aresta que os liga.


4. Uma vez que o algoritmo encontra o menor caminho entre a origem e um nó, ele o marca como visitado e o adiciona ao caminho. O processo continua até que todos os nós tenham sido visitados, retornando o caminho mais curto para cada nó a partir da origem.

Descrição da implementação 💻

1. Foi definida uma classe de heap de mínimo para a implementação do Dijkstra posteriormente.
2. Foi definida uma classe de grafo, para que o mesmo fosse construído com a base de dados.
3. A função calcula_caminho, dentro da classe grafo, foi definida e faz uso do algoritmo Dijkstra.
4. O arquivo.txt da base de dados foi convertido para um objeto grafo.
5. Uma interface de usuário para visualização em python foi feita com a biblioteca PySimpleGUI.
6. As bibliotecas MatPlotLib e Networkx são usadas para a visualização do grafo e o menor caminho.

Resultados

Links Importantes

• Slides da apresentação: https://docs.google.com/presentation/d/1mBEifS8Lc5fEZelkMCYgq7sHbQPOXUf9E9jQDVZ4L2s/edit?usp=sharing
• Video da apresentação do projeto: https://www.youtube.com/watch?v=Llw_FmcFQTY

Referências

• https://www.flightconnections.com/
• https://www.freecodecamp.org/news/dijkstras-shortest-path-algorithm-visual-introduction/#:~:text=Dijkstra%27s%20Algorithm%20finds%20the%20shortest,node%20and%20all%20other%20nodes
• https://www.youtube.com/watch?v=3vBx8GqlVT4&t=1968s
• icone do avião: Ao redor do mundo ícones criados por surang - Flaticon