Este capítulo contém a descrição detalhada da implementação do projeto. Também explica como fazer para executá-lo.
A figura abaixo mostra a interface principal do sistema.
O procedimento principal pode ser chamado através do predicado rodar, neste é definido todo o sistema de interface do usuário com o sistema. Apresentando uma lista de opções para que o usuário as escolha. Para carregá-lo é relativamente simples, suponha que você esteja com o código fonte no disquete, então o comando, a partir do prompt de uma linguagem Prolog (LPA Prolog), poderia ser o seguinte: consult('a:\grafos.pl'), rodar.
Depois de escolhida uma das opções, o predicado processar é chamado e executará a opção escolhida.
Antes de poder executar o algoritmo é necessário abrir um arquivo que contenha a representação de um grafo.
Agora vamos analisar o algoritmo em si. O predicado denominado algoritmo é que detém o controle principal sobre o processamento do mesmo. Abaixo está sendo mostrado o código dele.
algoritmo:-
obter_valores(Inicio, Fim),!,/* Obtêm os valores de inicio e fim */
mensagem(Inicio, Fim), /* Mostra mensagem. */
nos(X), /* Obtém o número de vértices do grafo */
cria_pesos(X), /* Cria a lista de vértices, com peso infinito */
seta_pesos(Inicio,0,0), /* Distância do Inicial é zero */
while([Inicio],[]), /* Loop, enquanto houver elementos na lista */
mostre_menor(Inicio,Fim). /* Mostra os valores obtidos */
Primeiro precisa-se saber quais os valores requeridos para o ponto de partida (Inicio) e ponto de chegada (Fim), então, baseado no número de vértices do grafo são inicializadas as distâncias de todos os elementos do grafo como infinitas (predicado cria_pesos), a seguir é atribuída a distância do vértice de inicio para zero, seta_pesos(Inicio,0,0) onde Inicio define o vértice corrente, o primeiro zero define a distância em que o vértice se encontra do ponto de partida e o segundo zero indica quem é o pai daquele vértice, zero significa que é o ponto de partida e que não tem pai.
É equivalente ao seguinte trecho de pseudocódigo:
Caminho-Mínimo ( Grafo, Inicio, Fim )
Para todo vértice V pertencente ao Grafo faça
Se
V = Inicio
V.Dist <- 0
Senão
V.Dist <- Infinita;
Lista <- Inicio;
.... /* Outro predicado, chamado while */
Mostre Resultado.
FIM.
O predicado while é executado continuamente até que não tenha mais vértices na lista para ser processado. Toda vez que o peso da distância de um vértice é modificado ele é inserido na lista para posteriormente ser executado. O código fonte deste predicado é mostrado abaixo:
while([]). /* Quanto a lista estiver vazia */
while([V|Lista]):-
no_adjacentes(V,Adjacentes), /* Encontra os vértices adjacentes */
for(Adjacentes,V,L1),/* Percorre todos os adjacentes, e retorna a lista dos que mudaram suas distâncias. */
insere(Lista,L1,L2), /* Concatena a nova lista com a antiga. */
while(L2).
Seu equivalente em pseudocódigo é:
Enquanto (Lista <> vazia) faça
V <- CAR(Lista);
Lista <- CDR(Lista) + Adjacentes(V)
..../* Predicado for */
O predicado for é executado toda vez que um vértice V tem elementos adjacentes. Todos os adjacentes são percorridos, e se a distância do adjacente A atual for maior que a distância de V somada com a distância existente entre o V e A então esta nova distância, Distância(V) + Distância(A,V), passará a ser a nova distância para A, e este adjacente será inserido no fim da lista.
Esta descrição pode ser visualizada no código abaixo:
for([],_,[]):-!. /* Quando não houver mais adjacentes */
for([A|Adjacentes],V,[A|L]):- /* Se Peso(A)>Peso(V)+Distancia(A,V) */
distancia(A,V,D),
menor_distancia(V,E,_),
menor_distancia(A,M,_),
D1 is D+E,
M>D1,
seta_pesos(A,D1,V), /* Atribui o novo peso ao vértice */
for(Adjacentes,V,L), !.
for([_|Adjacentes],V,L1):- /* Se Peso(A)<=Peso(V)+Distancia(A,V) */
for(Adjacentes,V,L1).
Código correspondente em pseudocódigo:
Para cada adjacente A de V faça
Se A.Dist > V.Dist + Distancia(A,V)
A.Dist <- V.Dist + Distancia(A,V);
A.Pai <- V;
Lista <- Lista + A;
Quando a lista ficar vazia significa que todos os possíveis caminhos existentes no grafo já foram percorridos e que o caminho mínimo foi encontrado. Só precisa-se mostrar agora o caminho mínimo que é implementado pelo predicado mostra_menor.
O código-fonte completo é apresentado no Apêndice.