- Nome: José Augusto Lajo Vieira Vital
- Universidade: Universidade Federal do Mato Grosso do Sul (FACOM - Faculdade de Computação)
- Matéria: Teoria dos Grafos e seus Algoritmos
- Professor: Vagner Pedrotti
Este projeto implementa o algoritmo de Dijkstra sem fila de prioridade. O algoritmo usa um vetor de distância e escolhe o vértice não visitado de menor valor no vetor por uma busca linear.
Para executar o programa, você precisa ter Python instalado em seu computador. Você pode baixar Python aqui.
Depois de instalar Python, você pode executar o programa com o seguinte comando:
python menorcaminho.py grafo.txt s
Caso o terminal retornar que o comando não foi identificado, tente colocar a versão do python instalada. ex.:
python3.11 menorcaminho.py grafo.txt s
Onde grafo.txt
é o arquivo que contém a descrição do grafo e s
é o vértice de origem.
O arquivo do grafo deve seguir o seguinte formato:
I n m
N i g- g+
E i j c T
Onde:
I n m
: Informações gerais do grafo, número de vértices e número de arestas.N i g- g+
: Uma linha para cada vértice contendo o número do vértice de 0 a n-1 com o grau de entrada e o grau de saída.E i j c
: Uma linha para cada arco do grafo, com o vértice de origem, vértice de destino e custo. O custo será sempre um inteiro não-negativo.T
: Indica o fim do arquivo.
Para todos os vértices (incluindo o próprio s
) em ordem numérica, o programa imprime na saída uma linha contendo:
- Caso exista um caminho de
s
atét
:P t v c v1 v2 ... vn
- Caso não exista caminho de
s
at
:U t
- Caso ocorra algum problema para leitura do grafo ou execução do algoritmo:
E