Version en ligne

Tutoriel : Le pathfinding avec Dijkstra

Table des matières

Le pathfinding avec Dijkstra
Qu'est-ce que le pathfinding ?
Histoire et principe de l'algorithme de Dijkstra
Application de l'algorithme à travers un exemple (non codé)
Limites et avantages de cet algorithme

Le pathfinding avec Dijkstra

Qu'est-ce que le pathfinding ?

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 ?

Histoire et principe de l'algorithme de Dijkstra

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 Dijkstra

Histoire et principe de l'algorithme de Dijkstra

Qu'est-ce que le pathfinding ? Application de l'algorithme à travers un exemple (non codé)

Histoire 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

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.

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 Dijkstra

0) 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)

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

Montpellier

Poitiers

Nantes

Aucun

Paris

Nantes

Poitiers

Bordeaux

Strasbourg

Arras

Vous allez regarder l'antécédent de Lyon : Paris, l'antécédent de Paris : Nantes, hop ! Vous êtes arrivés à Nantes en marche arrière !! (OK, je sors...)
Vous remettez le tout dans l'ordre, et vous avez votre chemin le plus court :

Nantes => Paris => Lyon
Évidemment, en regardant le graphe, cela semble évident et inutile d'utiliser un algorithme pour arriver à un résultat si trivial, mais imaginez un peu que vous modélisiez toutes les villes et toutes les routes de la France ? Ah ! ça devient intéressant là, non :p ?
Imaginez qu'en plus de ça, vous ajoutiez toutes les rues de chaque ville :diable: , ça deviendrait carrément indispensable...


Qu'est-ce que le pathfinding ? Application de l'algorithme à travers un exemple (non codé)

Application de l'algorithme à travers un exemple (non codé)

Histoire et principe de l'algorithme de Dijkstra Limites et avantages de cet algorithme

Vous avez tout compris ?

Euh oui, mais c'est peut-être encore un peu confus pour moi...

J'imagine ;) , c'est pour ça que nous allons voir un exemple concret pas à pas. Ne vous inquiétez pas, par souci d'ouverture, c'est un exemple n'utilisant aucun langage, que ce soit le C, le PHP, etc. (je suis gentil, hein ? :-° ).

Reprenons le graphe de tout à l'heure.

Graphe schematisant la France

Supposons que nous soyons à Bordeaux et que nous voulions aller à Strasbourg.

On initialise les tableaux

Nom du noeud

Poids

Déjà parcouru ?

Arras

-1

Non

Bordeaux

0

Non

Brest

-1

Non

Lyon

-1

Non

Marseille

-1

Non

Montpellier

-1

Non

Nantes

-1

Non

Paris

-1

Non

Poitiers

-1

Non

Strasbourg

-1

Non

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

On recherche le noeud avec le plus petit poids

Il s'agit de Bordeaux.

On liste les fils de Bordeaux

Aperçu des tableaux

Nom du noeud

Poids

Déjà parcouru ?

Arras

-1

Non

Bordeaux

0

Oui

Brest

-1

Non

Lyon

-1

Non

Marseille

-1

Non

Montpellier

-1

Non

Nantes

334

Non

Paris

-1

Non

Poitiers

237

Non

Strasbourg

-1

Non

Noeud

Antécédent du noeud

Arras

Aucun

Bordeaux

Aucun

Brest

Aucun

Lyon

Aucun

Marseille

Aucun

Montpellier

Aucun

Nantes

Bordeaux

Paris

Aucun

Poitiers

Bordeaux

Strasbourg

Aucun

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

Il s'agit de Poitiers.

On liste ses fils

Aperçu des tableaux

Nom du noeud

Poids

Déjà parcouru ?

Arras

-1

Non

Bordeaux

0

Oui

Brest

-1

Non

Lyon

-1

Non

Marseille

-1

Non

Montpellier

794

Non

Nantes

334

Non

Paris

575

Non

Poitiers

237

Oui

Strasbourg

-1

Non

Noeud

Antécédent du noeud

Arras

Aucun

Bordeaux

Aucun

Brest

Aucun

Lyon

Aucun

Marseille

Aucun

Montpellier

Poitiers

Nantes

Bordeaux

Paris

Poitiers

Poitiers

Bordeaux

Strasbourg

Aucun

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

Il s'agit de Nantes.

On liste ses fils

Aperçu des tableaux

Nom du noeud

Poids

Déjà parcouru ?

Arras

895

Non

Bordeaux

0

Oui

Brest

632

Non

Lyon

-1

Non

Marseille

-1

Non

Montpellier

794

Non

Nantes

334

Oui

Paris

575

Non

Poitiers

237

Oui

Strasbourg

-1

Non

Noeud

Antécédent du noeud

Arras

Nantes

Bordeaux

Aucun

Brest

Nantes

Lyon

Aucun

Marseille

Aucun

Montpellier

Poitiers

Nantes

Bordeaux

Paris

Poitiers

Poitiers

Bordeaux

Strasbourg

Aucun

Je vous invite à finir de trouver le chemin, et je vous laisse les états des tableaux des poids et des antécédents quand on est arrivé à Strasbourg, comparez-les avec les vôtres :) .

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

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

Chemin le plus court (roulement de tambours... :D ) :
1282 kilomètres parcourus !
Pour un total de Bordeaux -> Poitiers -> Paris -> Arras -> Strasbourg


Histoire et principe de l'algorithme de Dijkstra Limites et avantages de cet algorithme

Limites et avantages de cet algorithme

Application de l'algorithme à travers un exemple (non codé)

L'algorithme de Dijkstra, très puissant, admet quand même quelques limites :

Cependant il a plusieurs avantages :

Voilà, c'est fini !
J'espère avoir éclairé votre lanterne sur le fonctionnement de Mappy ^^ .
À noter cependant que ma manière d'implémenter peut probablement être améliorée. J'utilise pour ma part une boucle qui se répète jusqu'au noeud d'arrivée, on peut utiliser à la place une approche récursive, chacun ses goûts.


Application de l'algorithme à travers un exemple (non codé)