🗺️ C++ Route Planner

Um sistema de navegação simplificado escrito em C++ moderno (C++17) capaz de modelar uma malha rodoviária como um grafo e encontrar rotas entre diferentes cidades.

O programa constrói uma rede de conexões baseada em Teoria dos Grafos a partir de um arquivo de texto. Em seguida, permite consultas interativas utilizando o algoritmo de Busca em Profundidade (Depth-First Search - DFS) com backtracking para encontrar um caminho válido entre a cidade de origem e a cidade de destino, calculando também a distância total percorrida.

✨ Funcionalidades

• Representação por Grafos: Estrutura de dados baseada em listas de adjacência utilizando std::map para representar cidades e estradas.
• Algoritmo de Busca (DFS): Navegação pela malha rodoviária utilizando Busca em Profundidade com backtracking para explorar caminhos alternativos.
• Arquitetura Orientada a Objetos: Código modular utilizando polimorfismo e o padrão Strategy, permitindo substituir facilmente o algoritmo de busca por outras abordagens (como Dijkstra).
• Leitura e Validação de Arquivos Leitura segura de arquivos .txt delimitados por ponto e vírgula (;), com validação dos dados e tratamento de exceções.
• Interface CLI Amigável: Menu interativo que permite realizar múltiplas consultas sem recarregar a malha rodoviária.

🛠️ Pré-requisitos

Para compilar e executar este projeto, você precisará de:

• Um compilador C++ compatível com a norma C++17 (como g++ ou clang++).
• A ferramenta make para utilizar o Makefile incluído.

🚀 Como Compilar

O projeto acompanha um Makefile configurado para organizar os arquivos objeto durante a compilação.

Para compilar o programa, abra o terminal na pasta raiz do projeto e execute:

make

Isso criará o diretório obj/ (caso não exista) e gerará o executável routeplanner.

Caso queira remover os arquivos de compilação e o executável:

make clean

💻 Como Usar

O programa funciona via linha de comando e recebe um único argumento: o arquivo .txt contendo a malha rodoviária.

Formato do Arquivo de Entrada

Cada linha do arquivo deve representar uma estrada no formato:

Origem;Destino;Distancia

Exemplo:

Natal;João Câmara;80
Natal;Santa Cruz;115
Santa Cruz;Currais Novos;90

Sintaxe

./routeplanner <caminho_para_o_arquivo_txt>

Exemplo

./routeplanner data/rn.txt

Exemplo de Saída

Malha carregada com 12 cidades.

Cidade de origem: Natal
Cidade de destino: Currais Novos

Rota encontrada:
Natal -> Santa Cruz -> Currais Novos

Distancia total: 205 km

Deseja fazer outra consulta? (s/n):

Caso não exista um caminho entre as cidades informadas, o programa exibirá:

Nao ha rota disponivel entre Natal e Caico.

🏗️ Estrutura do Projeto

• main.cpp: ponto de entrada da aplicação e interface com o usuário.
• Cidade e Estrada: modelos de dados que representam os vértices e arestas do grafo.
• MalhaRodoviaria: armazena e gerencia a representação da malha utilizando listas de adjacência.
• BuscadorRota: interface abstrata que define o contrato para algoritmos de busca.
• BuscadorDFS: implementação da Busca em Profundidade (Depth-First Search).
• PlanejadorRotas: responsável por delegar as buscas e aplicar o padrão Strategy.
• LeitorArquivo: realiza a leitura e validação do arquivo de entrada.
• Rota: encapsula o resultado da busca, incluindo o caminho encontrado e a distância total.

👨‍💻 Autor

Desenvolvido por Hugo Araujo (2026).

GitHub: https://github.com/MrHuguitos