Autora: Luiza Kuze
Data: 04/07/2023
Projeto de PRG2
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
- 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.
# 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.csvApós essa sequência de comandos, o usuário deve realizar a entrada de dados e verificar os resutlados do programa.
É 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:
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.
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.
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.
O nodo atual é marcado como visitado e removido do conjunto de nodos não visitados.
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).
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. 🎈✨🎉
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.
Este projeto é licenciado sob a MIT License