Sommaire

Synthèse

La recherche de chemins, ou pathfinding, permet de relier des nœuds d’un graphe en utilisant des arcs prédéfinis. Ceux-ci sont associés à une longueur (ou coût). On peut ainsi chercher le chemin au coût le plus faible, que le coût soit en réalité un kilométrage, un temps ou encore un prix (par exemple l’essence consommée).

Plusieurs algorithmes existent, chacun ayant ses spécificités.

Lorsque l’on cherche principalement à savoir si un chemin existe, sans rechercher le plus court, on peut se tourner vers les algorithmes naïfs de recherche en profondeur ou en largeur. Si on sait globalement dans quelle direction aller, la recherche en profondeur peut être intéressante (à condition de bien préciser l’ordre de parcours des voisins).

La recherche en largeur donne généralement de meilleurs résultats et est surtout plus générique. Dans les deux cas, on avance de nœud en nœud et on mémorise les nouveaux nœuds adjacents découverts, que l’on visitera ultérieurement. Ce qui les différencie, c’est la structure utilisée pour stocker les voisins : une pile pour la recherche en profondeur et une file pour la recherche en largeur.

L’algorithme de Bellman-Ford permet, quant à lui, de trouver le chemin le plus court, et ce quel que soit le graphe. Il consiste à appliquer les arcs pour calculer ...