Le pathfinding avec Dijkstra

Histoire de l'algorithme et de son inventeur

Principe de l'algorithme de Dijkstra

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

• 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... ).

Étapes de l'algorithme de Dijkstra

0) Tout d'abord on initialise les tableaux

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

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

1
2
3
4
5
6
7
8
9
10
11

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...

1
2
3

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

1

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

1

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 jusque 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.

1
2
3

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

Antecedent(Noeud-fils) = Noeud-Père

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

On initialise les tableaux

On recherche le noeud avec le plus petit poids

On liste les fils de Bordeaux

• Nantes :
  • est-on déjà passé par Nantes ?
    => Non ;
  • kilométrage de Nantes > kilométrage de Bordeaux + distance Bordeaux-Nantes ?
    OU
    kilométrage de Nantes non défini (= -1) ?
    => Oui :
    • kilométrage de Nantes = kilométrage de Bordeaux + distance Bordeaux-Nantes ;
    • kilométrage de Nantes = 0 + 334 = 334 ;
    • antécédent de Nantes = Bordeaux.
• Poitiers :
  • est-on déjà passé par Poitiers ?
    => Non ;
  • kilométrage de Poitiers > kilométrage de Bordeaux + distance Bordeaux-Poitiers ?
    OU
    kilométrage de Poitiers non défini (= -1) ?
    => Oui :
    • kilométrage de Poitiers = kilométrage de Bordeaux + distance Bordeaux-Poitiers ;
    • kilométrage de Poitiers = 0 + 237 = 237 ;
    • antécédent de Poitiers = Bordeaux.

Aperçu des tableaux

Et on recommence ! On recherche le noeud non entouré avec le poids le plus faible

On liste ses fils

• Bordeaux :
  • est-on déjà passé par Bordeaux ?
    => Oui.
• Montpellier :
  • est-on déjà passé par Montpellier ?
    => Non ;
  • kilométrage de Montpellier > kilométrage de Poitiers + distance Poitiers-Montpellier ?
    OU
    kilométrage de Montpellier non défini (= -1) ?
    => Oui :
    • kilométrage de Montpellier = kilométrage de Poitiers + distance Poitiers-Montpellier ;
    • kilométrage de Montpellier = 237 + 557 = 794 ;
    • antécédent de Montpellier = Poitiers.
• Paris :
  • est-on déjà passé par Paris ?
    => Non ;
  • kilométrage de Paris > kilométrage de Poitiers + distance Poitiers-Paris ?
    OU
    kilométrage de Paris non défini (= -1) ?
    => Oui :
    • kilométrage de Paris = kilométrage de Poitiers + distance Poitiers-Paris ;
    • kilométrage de Paris = 237 + 338 = 575 ;
    • antécédent de Paris = Poitiers.

Aperçu des tableaux

Et on recommence ! On recherche le noeud non entouré avec le poids le plus faible

On liste ses fils

• Arras :
  • est-on déjà passé par Arras ?
    => Non ;
  • kilométrage de Arras > kilométrage de Nantes + distance Nantes-Arras ?
    OU
    kilométrage de Arras non défini (= -1) ?
    => Oui :
    • kilométrage de Arras = kilométrage de Nantes + distance Nantes-Arras
    • kilométrage de Arras = 334 + 561 = 895 ;
    • antécédent de Arras = Nantes.
• Bordeaux :
  • est-on déjà passé par Bordeaux ?
    => Oui.
• Brest :
  • est-on déjà passé par Brest ?
    => Non ;
  • kilométrage de Brest > kilométrage de Nantes + distance Nantes-Brest ?
    OU
    kilométrage de Brest non défini (= -1) ?
    => Oui :
    • kilométrage de Brest = kilométrage de Nantes + distance Nantes-Brest ;
    • kilométrage de Brest = 334 + 298 = 632 ;
    • antécédent de Brest = Nantes.
• Paris :
  • est-on déjà passé par Paris ?
    => Non ;
  • kilométrage de Paris > kilométrage de Nantes + distance Nantes-Paris ?
    OU
    kilométrage de Paris non défini (= -1) ?
    => Non.
    • Remarque : donc on n'y touche pas.

Aperçu des tableaux

Je ne continue pas afin d'épargner à ce tutoriel un alourdissement énorme et d'éviter qu'il ne fasse cinq kilomètres de long (et aussi parce que c'est assez long à mettre en forme pour moi ).
Toutes les différentes situations conditionnelles concernant les noeuds-fils ont été rencontrées, et il suffit de continuer en boucle, jusqu'à ce que le noeud de poids le plus faible soit le noeud d'arrivée (Strasbourg).

Tableau des antécédents

Noeud	Antécédents du noeud
Arras	Paris
Bordeaux	Aucun
Brest	Nantes
Lyon	Paris
Marseille	Montpellier
Montpellier	Poitiers
Nantes	Bordeaux
Paris	Poitiers
Poitiers	Bordeaux
Strasbourg	Arras

Tableau des poids

Nom du noeud	Poids	Déjà parcouru ?
Arras	760	Oui
Bordeaux	0	Oui
Brest	632	Oui
Lyon	1040	Oui
Marseille	965	Oui
Montpellier	794	Oui
Nantes	334	Oui
Paris	575	Oui
Poitiers	237	Oui
Strasbourg	1282	Oui

Dans cet exemple, on est passé par toutes les villes mais ce n'est pas toujours le cas.
Exemple : aller d'Arras à Brest.

Chemin le plus court (roulement de tambours... ) :
1282 kilomètres parcourus !
Pour un total de

Bordeaux -> Poitiers -> Paris -> Arras -> Strasbourg

• il demande une certaine masse de traitements quand le graphe devient grand. Par exemple, comme l'explique Haveo dans son tutoriel "Le pathfinding avec A*", quand la puissance matérielle est limitée, où que l'on souhaite traiter rapidement le problème du chemin le plus court, on peut utiliser d'autres algorithmes, tel A*, qui sont certes moins précis parfois, mais qui sont plus rapides et moins gourmands en ressources ;
• on ne peut pas affecter aux liaisons un poids négatif, sinon l'algorithme est faussé et retournera des résultats faux.

• contrairement à l'algorithme A* par exemple, il trouve toujours le chemin ayant le poids le plus faible ;
• il n'est pas si dur à comprendre et à mettre en place (surtout avec quelqu'un qui explique aussi bien que moi ) ;
• il peut être utilisé pour d'autres applications que la distance la plus courte d'un point à un autre.
  On peut remplacer les villes par d'autres choses. J'avais par exemple fait un graphe où les liaisons étaient des pertes d'argent et les noeuds étaient des choix économiques d'entreprise.