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 :
- Dijkstra : un algorithme glouton efficace, avec une complexité en temps de \(O(M \log _2 M)\) (avec \(M\) le nombre d'arcs du graphe), mais qui ne fonctionne que sur des graphes pondérés positivement.
- Bellman-Ford : un algorithme dynamique applicable sur n'importe quel type de pondération d'un graphe, mais avec une complexité en temps légèrement plus lente de \(O(NM)\) (avec \(N\) le nombre de nœuds du graphe).
- Floyd-Warshall :
Conclusion
Le problème du plus court chemin est extrêmement commun en algorithmique. On le retrouve dans beaucoup de domaines divers :
- GPS : comme évoqué en introduction, une carte routière est sans doute l'exemple le plus explicite lorsqu'on parle de plus court chemin. On souhaite chercher un trajet entre deux villes, et on peut utiliser différents graphes pondérés en fonction du critère de sélection (chemin le plus rapide en temps, chemin le plus court en distance, etc.).
- Jeu : dans les jeux vidéos, il est très courant de retrouver des graphes pondérés. Que ce soit pour déplacer des unités de manière intelligente en fonction de la carte (on parle alors de pathfinding), ou encore pour prendre des décisions selon différents critères qui peuvent influencer le reste de la partie, un algorithme de plus court chemin est très utile à connaître.
- Internet : lorsque deux machines communiquent entre elles sur Internet, elles passent obligatoirement par différents serveurs (à moins qu'elles soient directement reliées entre elles, mais ce n'est pas le cas ici). Il est fondamental de pouvoir choisir le chemin à prendre afin d'avoir un délai de communication minimal. On peut alors voir ce problème comme une forme de plus court chemin où les serveurs représenteraient des nœuds du graphe, et les pondérations seraient le délai de communication.
- Transport : quand on livre un colis, il y a souvent plusieurs moyens de transport à notre disposition. Chacun permet de se rendre d'un point A à un point B, coûte une certaine somme d'argent et met une durée prédéfinie pour se déplacer. On peut représenter ce problème sous forme d'un graphe pondéré, et le but de l'entreprise serait de trouver un chemin entre A et B pouvant alterner les formes de transports et minimisant par exemple le temps de trajet (en général, une entreprise cherchera aussi à minimiser le coût de transport).
- Finance : on a vu les cycles améliorants comme un concept péjoratif, cependant ils sont parfois très utiles comme en finance, où trouver ce genre de cycle peut être avantageux et permet de gagner de l'argent facilement. Si l'on imagine un graphe pondéré de multiples transactions bancaires (par exemple lorsque vous convertissez des euros en dollars), si on arrive à trouver un cycle améliorant dans ce graphe, cela signifie qu'on peut convertir en "boucle" et gagner encore plus d'argent à chaque tour.
- Génétique : lorsqu'on a deux chaînes d'ADN sous la forme d'une suite de nucléotides comme "AGGCTATGGC" et "ATGCAATGCC", et que l'on souhaite trouver le nombre minimum de mutations à appliquer à une chaîne pour se retrouver avec l'autre, on peut utiliser un algorithme de plus court chemin. Ce problème n'est pas restreint au domaine de la génétique, et il est assez fréquent de vouloir transformer une chaîne en une autre en un minimum d'opérations. Le graphe représenterait les différents états de la chaîne, et les arcs pourraient être une opération (avec comme pondération le coût de cette transformation). On peut aussi appliquer cette idée de graphe implicite à des nombres, ou tout autre forme de structure pouvant subir des modifications diverses (ajout, suppression, transformation, etc.).
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.