Plus court chemin

Publié : 22/05/2016 · Modifié : 22/05/2016


Introduction

Comment votre GPS peut-il connaître le plus court chemin entre Paris et Grenoble aussi facilement ? De manière générale, on peut se demander comment calculer l'itinéraire entre deux points donnés d'une carte de telle sorte que la distance soit minimale ? On pourrait aller encore plus loin dans la généralisation, en représentant notre carte comme un graphe et en transformant la question en : quel est le plus court chemin entre un nœud A et B dans un graphe pondéré ?

Il existe différentes manières de répondre à cette question, et la réponse varie souvent en fonction du graphe donné en entrée de notre algorithme (pondéré positivement, négativement, dense, creux, etc.). Savoir reconnaître un problème de plus court chemin est donc important, et utiliser le bon algorithme l'est encore plus. Ces algorithmes ne se limitent pas à la création d'un simple GPS rudimentaire, mais peuvent aller bien plus loin et servent de base à de nombreuses autres applications.

Algorithmes

Une liste non exhaustive d'algorithmes essentiels permettant de résoudre le problème du plus court chemin :

Conclusion

Le problème du plus court chemin est extrêmement commun en algorithmique. On le retrouve dans beaucoup de domaines divers :

Les applications des algorithmes de plus court chemin sont très vastes, et il est fondamental d'en comprendre l'utilité. Ce problème de plus court chemin dans un graphe introduit aussi de nouveaux énoncés, comme le fameux problème du voyageur de commerce qui consiste à trouver un plus court chemin parcourant tous les nœuds d'un graphe pondéré une seule fois seulement, en finissant le trajet sur le nœud de départ. Cette question, d'apparence assez simpliste, représente en réalité un problème dit NP-complet pour lequel on ne connaît pas de solution en un temps polynomial. Ce n'est pas le seul problème dans cette catégorie, et les utilisations connexes du plus court chemin sont loin d'être toutes aussi triviales qu'on peut l'imaginer.