%  calcul d'un chemin le plus court dans un reseau  algorithme de Dijkstra
%
%      mindist(Etiquettes permanentes d'entree,
%              Etiquettes permanentes de sortie,
%              Etiquettes temporaires d'entree)
mindist(Perms, Perms,[]).
mindist([(N1,D1)|P1],P2,T1):-
          liste_des((N,Long),arc(N1,N,Long),Voisins),
	  changer_les_voisins(Voisins,D1,T1,[(N2,D2)|T2]),
	  mindist([(N2,D2),(N1,D1)|P1],P2,T2).

%       version de setof qui renvoie la liste vide au lieu d'echouer 
liste_des(A,B,C):-setof(A,B,C),!.
liste_des(_,_,[]).

%       changer_les_voisins (Liste de couples (noeud,longueur),
%                            distance de l'origine jusqu'ici,
%                            etiquettes temporaires d'entree,
%                            etiquettes temporaires de sortie)
changer_les_voisins([],D,T,T).
changer_les_voisins([(N1,L1)|V1],D,T1,T3):-
          D1 is D + L1,
	  changer_un_voisin((N1,D1),T1,T2),
	  changer_les_voisins(V1,D,T2,T3).

%       changer un voisin (Couple (noeud, distance de l'origine),
%                          etiquettes temporaires d'entree,
%                          etiquettes temporaires de sortie)
changer_un_voisin(C,[],[]).	  
changer_un_voisin((N,D),[(N1,D1)|T1],[(N,D)|T2]):-
          D<D1,
	  oter(N,[(N1,D1)|T1],T2),!.
changer_un_voisin(C,[C1|T1],[C1|T2]):-
          changer_un_voisin(C,T1,T2).

%         oter(noeud, 
%              liste de couples d'entree, 
%              liste de couples de sortie)
oter(N,[(N,_)|T1],T1):-!.
oter(N,[(N1,D1)|T1],[(N1,D1)|T2]):-oter(N,T1,T2).

%         reseau exemple
arc(a,b,1).
arc(a,c,3).
arc(b,c,1).
arc(c,b,1).
arc(b,d,4).
arc(c,d,1).
arc(d,e,1).
arc(b,e,1).
arc(a,e,5).

%    test des distances sur le reseau a partir de a 
test(X) :- mindist([(a,0)],X,[(b,100),(c,100),(d,100),(e,100)]).

/*  résultats

| ?- test(X).

X = [(d,3),(e,2),(c,2),(b,1),(a,0)] ? 

yes
| ?- setof((X,Y),arc(X,Y,Z),L).

L = [(a,b),(b,c),(b,e),(c,b),(c,d),(d,e)],
Z = 1 ? ;

L = [(a,c)],
Z = 3 ? ;

L = [(b,d)],
Z = 4 ? ;

L = [(a,e)],
Z = 5 ? ;

no
| ?- setof((X,Y,Z),arc(X,Y,Z),L).

L = [(a,b,1),(a,c,3),(a,e,5),(b,c,1),(b,d,4),(b,e,1),(c,b,1),(c,d,1),(d,...,...)] ? ;

no