O algoritmo de Dijkstra foi concebido pelo cientista da computação holandês Edsger Dijkstra como uma técnica para encontrar o caminho mais curto entre dois nós em um grafo ponderado. Ele é particularmente útil em problemas de roteamento em redes, como em sistemas de navegação e em telecomunicações.
Este é um programa em C desenvolvido para calcular caminhos mínimos em grafos usando o algoritmo de Dijkstra. Ele permite encontrar o caminho mais curto entre dois vértices em um grafo ponderado.
Entrada de grafo
: Permite ao usuário fornecer um grafo ponderado como entrada, especificando os vértices e as arestas com seus respectivos pesos.Cálculo de menor caminho
: Utiliza o algoritmo de Dijkstra para encontrar o menor caminho entre dois vértices especificados pelo usuário.Saída de resultados
: Apresenta o caminho mais curto encontrado e seu custo total.
Para utilizar este programa, siga estas etapas simples:
Compilação
: Utilize o makefile fornecido executando o comandomake
no terminal.Execução
: Execute o programa compilado usando o comando./grafo
.Entrada de dados
: Informe o número de cidades no grafo, suas coordenadas e os caminhos entre elas, se desejar gerar caminhos aleatórios.Escolha de operação
: Selecione a operação desejada: exibir lista de adjacência ou calcular o caminho mínimo entre duas cidades.Visualização dos resultados
: Observe os resultados apresentados na tela, incluindo o caminho mais curto encontrado e seu custo total.
Se você quiser contribuir para este projeto, sinta-se à vontade para abrir problemas ou enviar solicitações de recebimento!
Este projeto foi desenvolvido como trabalho para a disciplina de Estrutura de Dados (EDDA3), ministrada pelo Professor Marques Sousa (@marquesmoreirasousa) em outubro de 2020.