Le pathfinding avec Dijkstra

Introduction du cours

Bonjour !
Aujourd'hui nous allons étudier un algorithme assez connu (enfin, connu, c'est relatif bien sûr :p ) : l'algorithme de Dijkstra.
Cet algorithme sert à trouver le chemin le plus court d'un point à un autre. Pour vous c'est facile, mais votre ordinateur, lui, est bête et ne sait pas aller de chez vous à chez Mamie par le chemin le plus court (eh non... :euh: ).
Pour la suite, c'est par ici :pirate: !

Qu'est-ce que le pathfinding ?

C'est l'histoire du livreur de pizzas, contraint de livrer ses commandes en moins d'une demi-heure avec pour seule arme un scooter faiblard et poussif. C'est aussi l'histoire de Monsieur Dupont qui, valise à la main, se rend à la gare de Strasbourg, direction Biarritz, sans bien savoir par où passer. C'est encore l'histoire du petit Epsien, synchronisant ses courses au Leclerc du coin avec le feu tricolore et qui cherche à épargner ses petits mollets. C'est enfin l'histoire d'Internet qui permet le transfert de tous types de données dans le monde entier via... quelle route, au fait ?

Le pathfinding est le fait de chercher à aller d'un point à un autre en trouvant le chemin le plus adapté (chemin le plus court, le plus rapide, uniquement sur autoroute, etc.).
Je vous invite à lire la définition du pathfinding sur Wikipédia qui est, je trouve, très complète.

J'ajoute que contrairement à l'algorithme A*, l'algorithme de Dijkstra est moins rapide et nécessite souvent plus de traitement, mais trouve le chemin le plus court.
Passons maintenant aux choses sérieuses :pirate: .

Histoire et principe de l'algorithme de DijkstraHistoire de l'algorithme et de son inventeur

L'algorithme de Dijkstra a été trouvé par M. Dijkstra (si, si, je vous jure :p ), Edsger de son prénom. Pour plus d'informations, vous pouvez consulter sa fiche sur Wikipédia, mais pour faire court, il a notamment trouvé cet algorithme du chemin le plus court, et a beaucoup participé au développement de langages tels l'ALGOL ou fait avancer les méthodes de programmation en se battant contre l'usage du GOTO en faveur d'une structure If - Then - Else à travers un article qu'il nomma "A case against the GOTO statement".

Principe de l'algorithme de Dijkstra

L'algorithme de Dijkstra se découpe en plusieurs parties.

Prérequis

• Savoir ce qu'est un graphe et l'interpréter.
  Ceci est un graphe de liaison représentant vaguement la France, nous l'utiliserons afin d'illustrer ce tutoriel :) .

  Ce graphe est composé de 2 types d'objets : les noeuds, représentant des villes (ici dans des rectangles ou des ellipses), et les arêtes (les jointures entre différents noeuds), étant chacune affectée d'un poids (ici le nombre de kilomètres séparant chaque ville l'une de l'autre).

• Chaque noeud doit avoir au minimum une liaison.

Le principe

Le principe de l'algorithme de Dijkstra est de trouver le chemin ayant le poids le plus faible entre 2 noeuds, sachant que le poids d'un chemin est la somme des poids des arêtes qui le composent.

Euh...

En clair, sur ce graphe, l'algorithme va trouver le chemin le plus court en distance (poids du chemin = sa longueur en km), sachant que la longueur du chemin est égale à la somme des longueurs de chaque arête le composant (poids d'une arête = sa longueur).
Compris ?

Compris ! Mais comment l'ordinateur va-t-il faire ?

La démarche algorithmique n'est pas évidente à trouver, même pour les humains. Pour l'appliquer il va nous falloir deux tableaux.

• Un tableau à 3 lignes, que l'on va appeler "tableau des poids" contenant :

  • dans la première ligne, la liste des noeuds (désignés soit par leur nom, soit plutôt par un numéro) ;

  • dans la seconde ligne, un poids affecté à chaque noeud ;

  • dans la troisième ligne, une variable vrai ou faux, qui servira à savoir si l'on est déjà passé par ce noeud.

• Un autre tableau à une dimension, que l'on nommera "tableau des prédécesseurs" contenant ce que nous allons appeler les prédécesseurs de chaque noeud, c'est-à-dire le "noeud-père" qui précède le noeud dans le chemin que l'on prend pour y aller.
  Exemple : si pour aller de Nantes à Strasbourg je suis ce trajet (cf. : graphe) : Strasbourg => Arras => Nantes, le prédécesseur de Nantes sera Arras, le prédécesseur de Arras sera Strasbourg, et Strasbourg lui, n'aura pas de prédécesseur (le pauvre... :euh: ).

Cela peut sembler un peu confus, mais accrochez-vous, je vais expliciter un peu.
Prenons un exemple, reprenant le graphe que je vous ai donné ci-dessus.
Supposons que l'on veuille aller de Brest à Montpellier, en prenant le chemin le plus court en distance.

Étapes de l'algorithme de Dijkstra0) Tout d'abord on initialise les tableaux

Concernant le tableau des poids, on va mettre tous les poids à -1, montrant par là qu'aucun poids n'a encore été affecté à un noeud, et on va mettre toutes les variables oui ou non à non, car on n'est passé par aucun noeud (ce qui est logique vu que l'algorithme n'a pas encore commencé son travail ^^ ).
Ensuite, on met le poids du point de départ à 0 (bah oui, de Brest à Brest, il y a bien 0 km... ;) ).

Nom du noeud

Poids

Déjà parcouru ?

Arras

-1

Non

Bordeaux

-1

Non

Brest

0

Non

Lyon

-1

Non

Marseille

-1

Non

Montpellier

-1

Non

Nantes

-1

Non

Paris

-1

Non

Poitiers

-1

Non

Strasbourg

-1

Non

Puis on met à 0 le tableau des antécédents.

Noeud

Antécédent du noeud

Arras

Aucun

Bordeaux

Aucun

Brest

Aucun

Lyon

Aucun

Marseille

Aucun

Montpellier

Aucun

Nantes

Aucun

Paris

Aucun

Poitiers

Aucun

Strasbourg

Aucun

1) On recherche le noeud non parcouru ayant le poids le plus faible et on indique donc qu'on l'a parcouru

La première fois, il s'agit forcément du noeud de départ. On met donc la variable oui ou non de Brest à oui.

2)On va rechercher ce que l'on appelle "les fils" du noeud où l'on se trouve

Si l'on découvre des fils au noeud, on va effectuer une condition sur chaque fils que l'on a trouvé :

SI ( le noeud-fils n'a pas encore été parcouru ) ET QUE ( Poids(Noeud-père) + Poids(Liaison Noeud-père/Noeud-fils) < Poids(Noeud-fils) ) OU Poids(Noeud-fils) = -1  {     Poids(Noeud-fils) = Poids(Noeud-père) + Poids(Liaison Noeud-père/Noeud-fils)     Antecedent(Noeud-fils) = Noeud-Père }

Pourquoi on fait ça ? Et pourquoi on change les poids et les antécédents ? J'aimais bien les anciens, moi... :euh:

Décortiquons un peu ce code :) .

SI ( le noeud-fils n'a pas encore été parcouru ) ET QUE ( Poids(Noeud-père) + Poids(Liaison Noeud-père/Noeud-fils) < Poids(Noeud-fils) ) OU Poids(Noeud-fils) = -1

Que veux dire cette condition ?

SI ( le noeud-fils n'a pas encore été parcouru )

Cette ligne vérifie que l'on n'a pas encore parcouru le noeud-fils (si, si, je vous jure :p ).
En effet, en réfléchissant un peu, si on a déjà parcouru le noeud-fils, c'est que la distance (Point de départ-Noeud fils) est inférieure à la distance (Point de départ-Noeud père) et que donc le Noeud-fils ne nous intéresse plus.

Poids(Noeud-père) + Poids(Liaison Noeud-père/Noeud-fils) < Poids(Noeud-fils)

• Poids(Noeud-père) est le poids pour aller jusqu'au Noeud-père. Ici cela représente la distance parcourue du noeud de départ jusqu'au noeud où l'on se trouve ;

• Poids(Liaison Noeud-père/Noeud-fils) représente ici la distance entre le Noeud-père où l'on se trouve, et le Noeud-fils ;

• Poids(Noeud-fils) représente la distance à parcourir pour aller du noeud de départ au Noeud-fils.

Concrètement, cela veut dire que la distance pour aller du départ au Noeud-fils, en passant par le Noeud-père où l'on se trouve, est plus petite que la distance pour aller du départ au Noeud-fils que l'on avait déjà trouvée en passant par un autre chemin.

Si on se trouve dans ce cas précis alors notre condition est validée, on exécute ce code :

Poids(Noeud-fils) = Poids(Noeud-père) + Poids(Liaison Noeud-père/Noeud-fils) Antecedent(Noeud-fils) = Noeud-Père

On change donc le poids du Noeud-fils, en mettant celui du chemin passant par le Noeud-père, et on indique dans le tableau d'antécédents, que l'étape précédente du Noeud-fils est le Noeud-père.

3) On boucle en retournant à l'étape 1) tant que...

Tant que le noeud ayant le poids le plus faible n'est pas le noeud d'arrivée.
En effet, quand le noeud ayant le poids le plus faible sera le noeud d'arrivée, cela voudra dire que l'on a trouvé le chemin le plus court pour y aller en partant du noeud de départ.

Le tour est joué :magicien: !

Oui mais... comment je retrouve ce chemin ??

C'est là que le tableau des antécédents est utile !
On va prendre l'antécédent du noeud d'arrivée (dans notre exemple, Montpellier), puis l'antécédent de l'antécédent de Montpellier, puis l'antécédent de l'antécédent de l'antécédent de Montpellierpuis l'antécédentde l'antécédent de...
Enfin bref, vous avez compris ^^ .
Exemple : supposons qu'à la fin de l'exécution de l'algorithme, vous avez un tableau d'antécédents qui ressemble à ça, et que vous cherchiez à aller de Nantes à Lyon.

Noeud

Antécédent du noeud

Arras

Nantes

Bordeaux

Nantes

Brest

Nantes

Lyon

Paris

Marseille

Aucun