Grafo |
Representação |
|
|
inf(1000) nos(3) n_adjacentes(1,[2,3]) n_adjacentes(2,[1,3]) n_adjacentes(3,[1,2]) distancia(1,2,2) distancia(2,1,2) distancia(1,3,1) distancia(3,1,,1) distancia(2,3,4) distancia(3,2,4) |
Abaixo está sendo apresentado o pseudocódigo do algoritmo implementado:
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;
Enquanto (Lista <> vazia) faça
E <- CAR(Lista);
Lista <- CDR(Lista);
Para cada adjacente A de E faça
Se A.Dist > E.Dist + Distancia(A, E)
A.Dist <- E.Dist + Distancia(A, E);
A.Pai <- E;
Lista <- Lista + A;
Mostre Resultado.
Fim.
Os seguintes predicados estão disponíveis para serem usados ao representar o grafo na base:
n_nos(NUMERO): onde a variável NUMERO determina o número de nós que o grafo possui.
no_adjacentes(NO,ADJACENTES) : onde cada vértice que compõe o grafo é armazenado na base, juntamente com seus vértice adjacentes.
distancia(VERTICE1,VERTICE2,DISTANCIA): representa a distância existente entre os vértices 1 e 2.
inf(INIFINITO): representa a distância máxima que pode existir entre dois vértices.
Exemplo:
Grafo |
Representação |
|
|
inf(1000) nos(3) n_adjacentes(1,[2,3]) n_adjacentes(2,[1,3]) n_adjacentes(3,[1,2]) distancia(1,2,2) distancia(2,1,2) distancia(1,3,1) distancia(3,1,,1) distancia(2,3,4) distancia(3,2,4) |
