%
% Dijkstra
%   + Start        : Point de départ
%   + Finish       : Point de d'arrivée
%   - ShortestPath : Chemin le plus court
%   - Len          : Longueur de ce chemin
%


dijkstra(Start, Finish, ShortestPath, Len) :-
 dijk( [0-[Start]], Finish, RShort, Len),
 reverse(RShort, ShortestPath).



% Le dernier point visité est le point d'arrivée => on s'arrête
%

dijk( [ Len-[Fin|RPath] |_], Fin, [Fin|RPath], Len) :- !.


dijk( Visited, Fin, RShortestPath, Len) :-
 % Recherche du meilleur candidat (prochain point à ajouter au graphe)
 %   et appel récursif au prédicat
 %

 bestCandidate(Visited, BestCandidate),
 dijk( [BestCandidate|Visited], Fin, RShortestPath, Len).



%
% Recherche toutes les arrêtes pour lesquelles on a:
%  - un point dans le graphe (visité)
%  - un point hors du graphe (candidat)
%
% Retourne le point qui minimise la distance par rapport à l'origine
%


bestCandidate(Paths, BestCandidate) :-

 % à partir d'un point P1 :

 findall(
    NP            % on fait la liste de tous les points P2 tels que:
 ,
   (
     member( Len-[P1|Path], Paths),  % - le point P2 a déjà été visité
     troncon(P1,P2,Dist),                % - il existe un arc allant de P1 à P2, de distance Dist
     \+isVisited(Paths, P2),         % - le point P2 n'a pas encore été visité

     NLen is Len+Dist,               % on calcule la distance entre l'origine et le point P2

     NP=NLen-[P2,P1|Path]            % on met chaque élément de la liste sous la forme: Distance-Chemin
                                     % pour pouvoir les trier avec le prédicat keysort/2
   )
 ,
   Candidates
 ),

 % On trie et on retient le chemin le plus court
 minimum(Candidates, BestCandidate).



%
% Sort le meilleur candidat parmi une liste de candidats
% (= celui de chemin le moins long)
%

minimum(Candidates, BestCandidate) :-
 keysort(Candidates, [BestCandidate|_]).



%
% Teste si un point P a déjà été visité
%

isVisited(Paths, P) :-
 memberchk(_-[P|_], Paths).