vignette|Exemple d'un plus court chemin du sommet A au sommet F : (A, C, E, D, F). En théorie des graphes, le problème de plus court chemin est le problème algorithmique qui consiste à trouver un chemin d'un sommet à un autre de façon que la somme des poids des arcs de ce chemin soit minimale.
Variantes du problème du plus court chemin Il existe de nombreuses variantes de ce problème suivant que le graphe est fini, orienté ou non, que chaque arc ou arête possède ou non une valeur qui peut être un poids ou une longueur. Un chemin le plus court entre deux nœuds donnés est un chemin qui minimise la somme des valeurs des arcs traversés. Pour calculer un plus court chemin, il existe de nombreux algorithmes, selon la nature des valeurs et des contraintes supplémentaires qui peuvent être imposées. Dans de nombreux cas, il existe des algorithmes de complexité en temps polynomiale, comme l'algorithme de Dijkstra dans des graphes avec poids positifs. En revanche, lorsque des contraintes supplémentaires comme des fenêtres de temps sont ajoutées, le problème peut devenir NP-difficile.
L'exemple d'application le plus courant est la recherche d'un trajet le plus court entre deux agglomérations. Ce problème d'apparence facile, puisqu'il s'agit simplement d'additionner les distances kilométriques, devient plus compliqué si on veut en déduire le temps de parcours, car l'intensité du trafic, le temps de traversée des agglomérations, sont des contraintes additionnelles. La recherche de chemin est au contraire un problème d'intelligence artificielle qui se rattache à la planification. Il consiste à trouver comment se déplacer dans un environnement entre un point de départ et un point d'arrivée en prenant en compte différentes contraintes. Il devient ardu lorsque diverses contraintes additionnelles (exécution en temps réel, présence d'incertitudes, contrainte de ressources, environnement évolutif, etc.) doivent être prises en compte.
Poids des arcs
Le problème et ses solutions dépendent d'abord de la nature des poids : chaque arc est doté d'un poids qui est un nombre réel. Les différents cas considérés sont : Les poids sont tous positifs : Dans ce cas, l'algorithme de Dijkstra permet de résoudre le problème du plus court chemin d'un sommet donné aux autres sommets en complexité en temps pour un graphe à arcs et sommets. Les poids sont quelconques, mais il n'y a pas de circuit de poids négatif (pas de circuit absorbant) : Dans ce cas, l'algorithme de Bellman-Ford permet de tester s'il existe un circuit absorbant et, en absence d'un tel circuit, de trouver un plus court chemin en temps . Les poids sont quelconques : Cette variante est NP-difficile, comme on peut le voir en considérant la réduction du problème du chemin hamiltonien NP-complet qui consiste à fixer le poids des arcs à .
Variantes du problème
On distingue essentiellement deux variantes du problèmes : Recherche à partir d'un sommet donné () On fixe un sommet , la source ou l'origine, et on cherche un chemin de longueur minimale de cette source à tous les sommets. Les algorithmes les plus importants sont L'algorithme de Dijkstra dans le cas de poids positifs L'algorithme de Bellman-Ford dans le cas de poids quelconques. Des variantes sont : L'algorithme A* est un algorithme basé sur une heuristique pour la recherche entre deux points donnés. L'algorithme de Viterbi permet de corriger, dans une certaine mesure, les erreurs survenues lors d'une transmission à travers un canal bruité. Le problème dual est la recherche d'un plus court chemin de tous les sommets vers un sommet commun (la cible). Ce problème se traite en inversant le sens des arcs.
Recherche pour tous les couples de sommets () On cherche un plus court chemin, ou au moins la longueur d'un tel chemin, pour tous les couples de sommets. L'algorithme de Floyd-Warshall donne la matrice des longueurs des plus courts chemins en temps pour un graphe à sommets, mais le graphe ne doit pas posséder de circuit de poids strictement négatif. L'existence d'un circuit négatif se voit par des valeurs négatives sur la diagonale principale. L'algorithme de Johnson résout le problème en absence de circuit négatifs, et peut être plus rapide que Floyd–Warshall dans des graphes creux.
Formulation comme programme linéaire Le problème du plus court chemin peut être formulé comme un problème d'optimisation linéaire comme suit.
Soit un graphe, avec deux sommets distingués (la source ou l'origine) et (le but ou le puits) ; on note le coût de l'arc . On considère le programme linéaire en les variables suivant
minimiser avec les contraintes et, pour tout i,
L'explication intuitive est que est une variable qui sert à indiquer si l'arc fait partie ou non du plus court chemin trouvé: elle vaut 1 si c'est le cas, et 0 sinon. On cherche à choisir l'ensemble d'arcs de poids total minimal, pourvu que les arcs composent un chemin de s à t ; cette condition est représentée par la contrainte qui exprime que, pour tout sommet autre que s et t, le nombre d'arcs entrants choisis doit être égal au nombre d'arcs sortant, et ainsi l'ensemble forme un chemin de s à t.
Le programme dual de ce programme linéaire est maximiser avec les contraintes pour tout i,j. Pour toute solution réalisable du dual, les coûts réduits sont non négatifs et sur ces coûts réduits, l'algorithme A* se comporte essentiellement comme l'algorithme de Dijkstra.
Une solution du programme dual est un potentiel aux nœuds. On voit facilement que pour toute solution , le vecteur est aussi une solution pour tout . On peut en particulier choisir de sorte que . Ainsi la valeur à maximiser est .
Pour un chemin quelconque de à un sommet , la longueur peut être estimée
Ceci montre que le potentiel d'un nœud est une borne inférieure à la longueur d'un chemin. On trouve une solution optimale du programme dual en choisissant le potentiel d'un nœud comme la longueur du plus court chemin de à pour la fonction objectif .
Algorithme de Floyd-Warshall généralisé
La similitude entre l'algorithme de Warshall, l’algorithme de Floyd-Warshall et l'algorithme de McNaughton et Yamada s'explique par une structure algébrique sous-jacente, celle de demi-anneau. Cette interprétation a été présentée, en premier lieu, dans un article de Claude Pair en 1966, puis reprise dans un livre de Claude Pair et Jean-Claude Derniame. La première version en anglais n’apparaît qu'en 1974 dans le livre d'Aho, Hopcroft et Ullman. Elle est reprise ultérieurement, par Gondran et Minoux par exemple — Édition en anglais : ; ces derniers citent un article français de 1968 de Pierre Robert et Jacques Ferland..
Un demi-anneau est un ensemble muni de deux lois binaires et . La loi est associative, commutative et admet un élément neutre noté 0 ou . La loi est associative et distributive par rapport à . Elle admet un élément neutre noté 1 ou . L'algèbre de Boole est un exemple de demi-anneau en prenant , (ou) et (et).
Pour que l'algorithme de Floyd-Warshall généralisé fonctionne, il faut de plus supposer que le neutre de la loi soit absorbant pour la loi . Autrement dit, pour tout élément du demi-anneau, l'égalité doit être vérifiée.
Matrice associée à un graphe pondéré
Soit donné un graphe dont les sommets sont . On associe à chaque arc un poids (une longueur, une distance, une densité de trafic selon le problème) qui est un élément d'un demi-anneau (demi-anneau plus ou moins simple selon la nature du problème à traiter). La matrice associée au graphe pondérée est la matrice dont l'élément en position est si l'arc existe, et égal à 0 (le du demi-anneau) sinon.
Le poids d'un chemin est le produit, dans le demi-anneau, des poids de arcs qui le composent : . La longueur du plus court chemin de à est, dans ce formalisme la somme des poids de à . Si l'on note l'ensemble des chemins de à , le chemin cherché est un chemin dont le poids est .
Dans le cas où et , c'est le poids minimal d'un chemin reliant à .
Algorithme de Floyd-Warshall généralisé
Étant donné un graphe de matrice associée d'ordre , avec , on définit deux suites de matrices :
une suite de matrices par : et avec . Cette suite de matrices est telle que l'élément de la matrice est égal à la somme des poids des chemins de longueur au plus de à .
une autre suite de matrices par :
Cette suite de matrices est telle que les éléments ont pour valeur l'indice du premier point intermédiaire du chemin de à à l'étape .
Il s'ensuit que est l'indice du premier sommet intermédiaire entre et , le second sommet est donné par où , etc.
Applications
Existence des chemins joignant des sommets
C'est le problème de savoir, pour tout couple de sommets, s'il existe un chemin de à , ou de connaître, pour un sommet donné, les sommets accessibles à partir de . Ce problème de fermeture transitive se formule en choisissant un même poids pour chaque arc.
On peut donc résoudre le premier problème par l'algorithme de Warshall, le deuxième aussi par un simple parcours, en profondeur ou en largeur, à partir du somme s.
Distance minimum entre deux sommets
La distance minimum pour toute paire de sommets se calcule par l'algorithme de Floyd-Warshall, donc en prenant le demi-anneau tropical ou (max,+)-demi-anneau sur les nombres réels positifs ou nuls.
Chemins à capacité de trafic maximale entre deux sommets
La capacité de trafic possible sur un chemin est le minimum des capacités des arcs qui composent le chemin. Le chemin de capacité maximale est celui qui maximise ce minimum. On calcule les valeurs par l'algorithme de Warshall généralisé, en prenant et .
Réseaux routiers
Un réseau routier peut être considéré comme un graphe avec des poids positifs. Les nœuds représentent des croisements de routes et chaque arc du graphe est associé à un segment de route entre deux croisements. Le poids d'un arc peut correspondre à la longueur du segment de route associé, au temps nécessaire pour traverser le segment ou au coût de parcours du segment. En utilisant des graphes orientés, il est également possible de modéliser des rues en sens unique. Ces graphes ont des propriétés particulières en ce sens que certains arcs sont plus importants que d'autres pour les voyages à longue distance (typiquement les autoroutes). Cette propriété a été formalisée en utilisant un paramètre supplémentaire appelé .. Elle permet de calculer des chemins optimaux plus rapidement que dans les graphes généraux. L'idée première est que si on veut aller d'une petite ville à une autre, située assez loin, on a intérêt à chercher une grande ville près du lieu de départ, et une grande ville près de l'arrivée, et de combiner le chemin en passant par les deux grandes agglomérations.
Ces algorithmes travaillent en deux phases. Dans une première phase de prétraitement, le graphe est adapté pour permettre une interrogation rapide. La deuxième phase est la phase d'interrogation ; les nœuds de départ et d'arrivée sont alors connus, et comme le réseau est statique, le prétraitement peut être fait une fois pour toutes et être utilisé pour de nombreuses interrogations.
L'algorithme le plus rapide connu (en 2011) est appelé , et calcule les chemins les plus courts en quelques fractions de secondes.
Plus court chemin pour des poids dynamiques