Algorithmes sur les graphes en Prolog:
Dijkstra, Prim, Kruskal

Voici le fonctionnement de l'algorithme de Dijkstra :

1. On construit un graphe G' uniquement composé du point de départ
2. On fait la liste des arcs tels que
   • le point de départ appartienne à G'
   • le point d'arrivée appartienne à G (notre graphe de départ) mais pas à G'
3. Si la liste est vide, on s'arrête (il n'existe pas de chemin entre les points considérés)
4. A partir de cette liste, on sélectionne l'arc qui minimise la distance entre le point de départ et le nouveau point
5. On ajoute cet arc à G', ce qui ajoute également un point au graphe. On garde une trace du chemin ayant permis d'arriver au nouveau point
6. Si le point fraîchement ajouté correspond au point d'arrivée recherché, on s'arrête et on retourne le chemin complet (qui est le chemin le plus court).
7. Sinon, retour en 2.

Pour l'implémentation, nous représenterons chaque chemin de la manière suivante: DistanceChemin-CheminInversé.

Les chemins étant inversés, pour un chemin donné, on a directement accès au dernier point visité, celui-ci se trouvant en tête de liste. Ce n'est qu'à la fin de l'algorithme qu'on inversera la liste pour avoir le chemin dans le bon sens.

Par ailleurs, le fait de mettre sous cette forme (la distance en premier) permet de trier les chemins par ordre croissant grâce au prédicat keysort/2, ce qui facilite l'implémentation.

Voici une implémentation de l'algorithme de Dijkstra en Prolog :

%
% 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é
      arc(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).

L'implémentation en Prolog est finalement relativement simple.

L'étape 2, par exemple, est effectuée par le prédicat bestCandidate/2. Dans ce prédicat, pour chaque point déjà visité, on fait la liste des arcs partant de ce point et amenant à un point qui ne fait pas déjà partie du graphe en construction. Grâce au keysort, on détermine le chemin le plus court depuis l'origine (étape 4). Si aucun chemin n'est trouvé, le prédicat échoue (étape 3). Ceci se traduit en Prolog par:

  % à 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é
      arc(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
  keysort(Candidates, [BestCandidate|_]).

Il s'agit là de l'étape la plus difficile de l'algorithme, et pourtant c'est une traduction mot pour mot de la description de l'algorithme...

Optimisations possibles :

Pour faciliter l'implémentation, concernant la recherche du chemin le plus court, nous avons implémenté le prédicat minimum/2 de la manière suivante :

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

Il s'agit donc d'un tri à la suite duquel on ne garde que le premier élément de la liste (donc le minimum). L'algorithme de tri est de complexité O(n²), alors que la recherche d'un minimum est de complexité O(n) seulement. L'implémentation n'est donc pas optimale. Cependant, il faut garder à l'esprit que l'algorithme de tri est implémenté à bas niveau en Prolog, rendant le tri plus performant.

Dans le cas précédent, nous nous sommes intéressés aux performances concernant la vitesse. Cette implémentation nécessite l'utilisation de listes, consommatrices de mémoire. Dans le cas de graphes présentant de nombreux arcs, on souhaite économiser la mémoire. Pour ce faire, nous n'allons pas utiliser de listes. A la place, nous allons donner une définition formelle (en programmation logique) du chemin le plus court en 2 points.

La modification a lieu dans le prédicat bestCandidate/2. Dans l'implémentation suivante, nous vous recommandons de prêter une attention particulière aux commentaires, qui décrivent de manière formelle comment on définit la solution:

bestCandidate(Paths, BestCandidate) :-

  % Soient les points P1 et P2
  % tels que :

  member( Len1-[P1|Path1], Paths),  % - le point P1 a déjà été visité
  arc(P1,P2,Dist1),                 % - il existe un arc allant de P1 à P2
  \+isVisited(Paths, P2),           % - le point P2 n'a pas encore été visité

  NLen1 is Len1 + Dist1,            % NLen1 = Dist(Origine, P2)


  % L'arc P1->P2 est tel que :

  forall(  
    % Pour tout arc P3->P4
    % tel que :

    (
      member( Len2-[P3|_], Paths),  % - le point P3 a déjà été visité
      arc(P3,P4,Dist2),             % - il existe un arc allant de P3 à P4
      \+isVisited(Paths, P4),       % - le point P4 n'a pas encore été visité

      NLen2 is Len2 + Dist2         % NLen2 = Dist(Origine, P4)
    )
  ,

    % On cherche à obtenir :
    % P2 fournit le chemin le plus court depuis l'origine

    NLen1 =< NLen2

  ),

  
  % En cas d'ex-aequo, on ne garde qu'une seule solution
  !,


  BestCandidate = NLen1-[P2,P1|Path1].

Dans cette implémentation, on compare chaque candidat avec tous les autres candidats et on s'arrête dès que l'on a trouvé le point qui fournit le chemin le plus court. Dans le pire des cas la complexité est donc en O(n²) (même si en fait la recherche s'interrompt dès qu'un minimum est trouvé). Cependant, cette implémentation n'utilise pas de liste, requiert donc moins de mémoire et conviendra particulièrment bien aux graphes de taille importante.

Cette dernière implémentation illustre la manière dont on programme en Prolog : plutôt que de décrire les différentes étapes de résolution d'un algorithme (le "comment ?" de "comment trouver la solution ?"), on s'attache à décrire de manière formelle ce qu'est une solution (le "quoi ?": "qu'est-ce qu'une solution ?").

Afin de mieux comprendre cette implémentation, nous vous invitons à vous référer au cours portant sur Prolog et l'Algèbre Relationnelle, et plus particulièrement cette partie.

L'algorithme de Dijkstra ne s'applique que dans le cas d'un graphe pour lequel le poids des arcs est non négatif, ce qui constitue la majorité des graphes (cartes routières, réseaux divers...). Pour les graphes dont le poids des arcs peut être négatif, on doit avoir recours à l'algorithme de Bellman-Ford

L'algorithme de Bellman-Ford est moins rapide que l'algorithme de Dijkstra. Aussi, dans la majorité des cas (graphes dont le poids des arcs est non négatif), on utilisera Dijkstra.

Nous ne proposons pas d'implémentation pour Bellman-Ford car pour l'instant, nous n'avons pas eu de question à ce sujet sur le forum Prolog de developpez...