Skip to content
This repository has been archived by the owner on Sep 17, 2024. It is now read-only.
/ Melhor-Caminho Public archive

Projeto para encontrar a melhor rota entre duas cidades, em C++, utilizando o algoritmo de Dijkstra para calcular a menor distância a partir de um mapa de cidades armazenado em um arquivo CSV.

License

Notifications You must be signed in to change notification settings

luizakuze/Melhor-Caminho

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

16 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Melhor Caminho 🚗

Autora: Luiza Kuze
Data: 04/07/2023
Projeto de PRG2

Descrição 📌

O programa exibe a melhor rota possível entre duas cidades. A rota é apresentada como uma sequência de cidades desde a origem até o destino, juntamente com a distância total da viagem. As cidades devem ser inseridas através do teclado, e o resultado é exibido na tela.

Existe um "mapa" que é um arquivo csv que fornece informações sobre cada par de locais e a distância entre eles.

Cidade 1 Cidade 2 Distância (km)
Florianópolis São José 19
Florianópolis Biguaçu 24
São José Biguaçu 20
São José Palhoça 6
São José São Pedro de Alcântara 22
Biguaçu Antônio Carlos 17
São Pedro de Alcântara Antônio Carlos 10

parte do mapa com algumas cidades próximas a Florianópolis
arquivo: distancias.csv

Objetivos 🎯

  • Implementar um "mapa" da região analisada no programa.
  • Encontrar a menor rota entre duas cidades desse mapa.
  • Encontrar a distância da menor rota das cidades.
  • Tratamento de erros ao informar cidades inválidas.
  • Aprender sobre grafos e o algoritmo Dijkstra.
  • Adaptar o algoritmo de Dijkstra para a resolução do problema.

Funcionamento 💻

# Clonar o repositório do projeto 
git clone https://github.com/luizakuze/Melhor-Caminho

# Acessar o diretório 
cd Melhor-Caminho

# Compilar o projeto
g++ main.cpp funcoes.cpp -o projeto

# Executar o projeto (no linux)
./projeto distancias.csv

Após essa sequência de comandos, o usuário deve realizar a entrada de dados e verificar os resutlados do programa.

Implementação 📚

É um algoritmo de busca de menor caminho usado em grafos ponderados direcionados. Sua principal aplicação é encontrar a rota mais curta entre dois nodos em um grafo, levando em consideração os pesos associados às arestas.

A ideia para construção do mapa foi que cada nodo é uma cidade e as arestas são as distâncias entre as cidades. O passo foi o seguitne:

  1. Inicialização

Inicialmente, todas as distâncias para os nodos são definidas como infinito, exceto a distância para o nodo de origem, que é definida como zero. Um conjunto (geralmente uma fila de prioridade) é mantido para acompanhar os nodos não visitados.

  1. Seleção do Nodo Atual:

Em cada etapa, o algoritmo seleciona o nodo não visitado com a menor distância conhecida a partir da origem. Isso é feito de forma eficiente usando a estrutura linear "fila", que permite facilmente recuperar o nodo com a menor distância.

  1. Atualização das Distâncias:

O algoritmo visita os nodos adjacentes ao nodo atual e calcula as distâncias até esses nodos através do nodo atual. Se a nova distância calculada for menor do que a distância conhecida anteriormente, a distância é atualizada.

  1. Marcação de Nodos Visitados:

O nodo atual é marcado como visitado e removido do conjunto de nodos não visitados.

  1. Repetição:

Os passos 2~4 são repetidos até que todos os nodos tenham sido visitados ou até que o nodo de destino tenha sido visitado (se estivermos procurando a menor rota para um nodo específico).

  1. Resultado:

Após a conclusão do algoritmo, temos uma tabela que contém as menores distâncias conhecidas de origem para todos os nodos no grafo, bem como os predecessores que formam a menor rota para cada nodo. 🎈✨🎉

Tabela hash 📘

Dada a descrição sobre o algoritmo de Dijkstra acima, é visível a extrema importância da estrutura da tabela hash no projeto. Frisando os benefícios que o projeto ganhou ao utilizar ela:

  • Facilita a seleção eficiente do próximo nodo a ser explorado pelo algoritmo de Dijkstra, permitindo encontrar o nodo com a menor distância conhecida de forma rápida.
  • Permite a atualização rápida das distâncias mínimas dos nodos à medida que o algoritmo avança, garantindo que as informações estejam sempre atualizadas.
  • Após a conclusão do algoritmo, as tabelas hash são cruciais para construir a menor rota entre a cidade de partida e a cidade de destino.

Licença 📜

Este projeto é licenciado sob a MIT License

About

Projeto para encontrar a melhor rota entre duas cidades, em C++, utilizando o algoritmo de Dijkstra para calcular a menor distância a partir de um mapa de cidades armazenado em um arquivo CSV.

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published