Voir la source de Problème de plus court chemin

[[Fichier:Shortest path with direct weights.svg|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 (théorie des graphes)|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 (intelligence artificielle)|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 [[Système temps réel|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 <math>(x,y)</math> est doté d'un poids <math>w(x,y)</math> 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]] <math>O(m + n \log n)</math> pour un graphe à <math>m</math> arcs et <math>n</math> sommets. 
* Les poids sont quelconques, mais il n'y a pas de [[Circuit (théorie des graphes)|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  <math>O(nm)</math>. 
* Les poids sont quelconques : Cette variante est [[NP-difficile]], comme on peut le voir en considérant la réduction du   [[Graphe hamiltonien#Problème du chemin hamiltonien|problème du chemin hamiltonien]] [[Problème NP-complet|NP-complet]] qui consiste à fixer le poids des arcs à <math>-1</math>.

== Variantes du problème ==

On distingue essentiellement deux variantes du problèmes :
=== Recherche à partir d'un sommet donné ({{Citation étrangère|langue=en|Single source}}) ===
On fixe un sommet <math>s</math>, 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 ({{Citation étrangère|langue=en|All pair}}) ===
On cherche un plus court chemin, ou au moins la longueur d'un tel chemin, pour tous les couples <math>(s,t)</math> de sommets. 
* L'[[algorithme de Floyd-Warshall]] donne la matrice des longueurs des plus courts chemins en temps <math>O(n^3)</math> pour un graphe à <math>n</math> 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 [[graphe dense|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 <math>G=(S,A)</math> un graphe, avec deux  sommets distingués <math>s</math> (la source ou l'origine) et <math>t</math> (le but ou le puits) ; on note <math>w(i,j)</math> le coût de l'arc <math>(i,j)</math>. On considère le programme linéaire en les variables <math>x_{ij}</math> suivant 

:minimiser <math>\sum_{ij \in A} w(i,j) x_{ij}</math> 
avec les contraintes <math>x_{ij}\ge 0</math> et, pour tout ''i'',
: <math>\sum_j x_{ij} - \sum_j x_{ji} = \begin{cases}1&\text{si }i=s;\\ -1&\text{si }i=t;\\ 0&\text{sinon.}\end{cases}</math>

L'explication intuitive est que <math>x_{ij}</math> est une variable qui sert à indiquer si l'arc <math>(i,j)</math> 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 [[Optimisation linéaire|dual]] de ce programme linéaire est
:maximiser <math>y_t-y_s</math> 
avec les contraintes
:<math>y_j-y_i\le w(i,j)</math>   pour tout  ''i,j''. 
Pour toute solution réalisable <math>y</math> du dual, les coûts réduits <math>w'(i,j) = w(i,j) - y_j + y_i</math> sont non négatifs et sur ces coûts réduits, l'algorithme A* se comporte essentiellement comme l'algorithme de Dijkstra.

Une solution <math>y</math> du programme dual est un ''potentiel aux nœuds'' nennt man ein ''Knotenpotential''. On voit facilement que pour toute solution <math>(y_i)_{i \in S}</math>, le vecteur <math>(y_i + \delta)_{i \in S}</math>
est aussi une  solution pour tout <math>\delta \in \R</math>. On peut en particulier choisir <math>\delta</math> de sorte que <math>y_s = 0</math>. Ainsi la valeur à maximiser est <math>\max \; y_t</math>.

Pour un chemin quelconque <math>c</math> de <math>s</math> à un sommet <math>v \neq s</math>, la longueur peut être estimée 
:<math>
 w(c) = \sum_{(i,j) \in c} w(i,j) \geq \sum_{(i,j) \in c} y_j - y_i = y_v
</math>
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 <math>v \neq s</math> comme la longueur du plus court chemin de <math>s</math> à <math>v</math> pour la fonction objectif  <math>w</math>.

== Algorithme de Floyd-Warshall généralisé ==
{{loupe|demi-anneau}}
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<ref>{{Chapitre
| auteur = Claude Pair
| titre =  Sur des algorithmes pour des problèmes de cheminement dans les graphes finis
| titre ouvrage = Théorie des graphes (journées internationales d'études) -- Theory of Graphs (internainal symposium)
| éditeur = Dunod (Paris) et  Gordon and Breach (New York)
| année = 1966
| adresse = Rome (Italie)
| page début = 271
| auteur ouvrage = P. Rosentiehl
}}
</ref>, puis reprise dans un livre de Claude Pair et Jean-Claude Derniame<ref>{{Ouvrage
| auteur1=Jean Claude Derniame
| auteur2=Claude Pair
| titre=Problèmes de cheminement dans les graphes
| éditeur=Dunod (Paris)
| année=1971
| pages totales=182
}}
</ref>.  La première version en anglais n’apparaît qu'en 1974 dans le livre d'Aho, Hopcroft et Ullman<ref>{{Ouvrage
 | auteur1=Alfred V. Aho
 | auteur2=John E. Hopcroft
 | auteur3=Jeffrey D. Ullman
 | titre=The Design and Analysis of Computer Algorithms
 | lieu=Reading, Mass.
 | éditeur=[[Addison-Wesley]]
 | année=1974
 | pages totales=470
 | isbn=978-0-201-00029-0
}}</ref>. Elle est reprise ultérieurement,  par [[Michel Gondran|Gondran]] et Minoux par exemple<ref>{{Ouvrage
 |langue=fr
 |prénom1=Michel
 |nom1=Gondran
 |lien auteur1=Michel Gondran
 |prénom2=Michel
 |nom2=Minoux
 |titre=Graphes, dioïdes et semi-anneaux
 |sous-titre=nouveaux modèles et algorithmes
 |lieu=Paris
 |éditeur=Tec & Doc
 |année=2001
 |pages totales=xvi+415
 |isbn=2-7430-0489-4
 |sudoc=060235101
}} — Édition en anglais :  {{Ouvrage
 |langue=en
 |prénom1=Michel
 |nom1=Gondran
 |lien auteur1=Michel Gondran
 |prénom2=Michel
 |nom2=Minoux
 |titre=Graphs, Dioids and Semirings
 |sous-titre=New Models and Algorithms
 |lieu=Dordrecht
 |éditeur=Springer Science & Business Media
 |collection=Operations Research/Computer Science Interfaces Series
 |numéro dans collection=41
 |année=2008
 |pages totales=xix+383
 |isbn=978-0-387-75450-5
 |zbl=1201.16038
 |sudoc=12874958X
 |lire en ligne=https://books.google.com/books?id=XudA1RktfCAC&printsec=frontcover
}}</ref>; ces derniers citent un article français de 1968 de Pierre Robert et Jacques Ferland<ref>{{article|auteur1= Pierre Robert|auteur2= Jacques Ferland
 | titre = Généralisation de l’algorithme de Warshall
 | journal = Revue française d’informatique et de recherche opérationnelle, série rouge
 | tome = 2 |numéro = 1 | année =1968 | pages = 71-85
 | url = http://www.numdam.org/item?id=M2AN_1968__2_1_71_0}}.</ref>.

Un [[demi-anneau]] est un ensemble muni de deux lois binaires <math>\oplus</math> et <math>\otimes</math>. La loi <math>\oplus</math> est associative, commutative et admet un [[élément neutre]] noté 0 ou <math>z</math>. La loi <math>\otimes</math> est associative et [[Distributivité|distributive]] par rapport à <math>\oplus</math>. Elle admet un élément neutre noté 1 ou <math>e</math>.  L'[[algèbre de Boole (structure)|algèbre de Boole]] est un exemple de demi-anneau en prenant <math>Q=\{0,1\}</math>,<math>\oplus=\vee</math> (ou) et <math>\otimes=\wedge</math>(et).

Pour que l'algorithme de Floyd-Warshall généralisé fonctionne, il faut de plus supposer que le neutre <math>e</math> de la loi <math>\otimes</math> soit absorbant pour la loi <math>\oplus</math>. Autrement dit, pour tout élément <math>x</math> du demi-anneau, l'égalité <math>x \oplus e = e</math> doit être vérifiée.

=== Matrice associée à un graphe pondéré ===

Soit donné un graphe <math>G</math> dont les sommets sont <math>\{1,\dots,n\}</math>.  On associe à chaque arc  <math>(i,j)</math> un poids <math>w(i,j)</math> (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 <math>(i,j)</math> est <math>w(i,j)</math> si l'arc <math>(i,j)</math> existe, et égal à 0 (le <math>z</math> du demi-anneau) sinon.

Le poids d'un chemin <math>c=(i_0,i_1,\ldots,i_d)</math> est le produit, dans le demi-anneau, des poids de arcs qui le composent :
:<math>w(c)=w(i_0,i_1)\otimes w(i_1,i_2) \otimes w(i_{d-1},i_d)</math>.
La longueur du plus court chemin de <math>i</math> à <math>j</math> est, dans ce formalisme la somme des poids de <math>i</math> à <math>j</math>. Si l'on note <math>\Gamma_{i,j}</math> l'ensemble des chemins de <math>i</math> à <math>j</math>, le chemin cherché est un chemin dont le poids est 
:<math>\bigoplus_{c \in \Gamma_{i,j}} w(c)</math>.

Dans le cas où <math>\oplus = \min</math> et <math>\otimes = +</math>, c'est le poids minimal d'un chemin reliant <math>i</math> à <math>j</math>.

=== Algorithme de Floyd-Warshall généralisé ===

Étant donné un graphe de matrice associée <math>A</math> d'ordre <math>n</math>, avec <math>a_{i,j}=w(i,j)</math>, on  définit deux suites de matrices : 

* une suite de matrices <math>A^{(k)}</math> par :
:<math>A^{(0)}=A</math> et 
:<math>A^{(k)}=\left(a_{i,j}^{(k)}\right)</math> avec <math>a_{i,j}^{(k)}=a_{i,j}^{(k-1)}\oplus \left(a_{i,k}^{(k-1)}\otimes a_{k,j}^{(k-1)}\right)</math>. 
:Cette suite de matrices est telle que l'élément <math>a_{i,j}^{(n)}</math> de la matrice <math>A^{(n)}</math> est égal à la somme des poids des chemins de longueur au plus <math>n</math>  de <math>i</math> à <math>j</math>. 

* une autre suite de matrices <math>D^{(k)}</math> par : 
:<math>d_{i,j}^{(0)} = \begin{cases}j&\text{si } (i,j) \text{ est un arc} \\ 0&\text{sinon }\end{cases}</math>
:<math>d_{i,j}^{(k)} = \begin{cases}d_{i,j}^{(k-1)} &\text{si } a_{i,j}^{(k)} = a_{i,j}^{(k-1)} \\ d_{i,k}^{(k-1)} & \text{sinon }\end{cases}.</math>
:Cette suite de matrices est telle que les éléments <math>d_{i,j}^{(k)}</math> ont pour valeur l'indice du premier point intermédiaire du chemin de <math>i</math> à <math>j</math> à l'étape <math>k</math>. 

Il s'ensuit que <math>d_{i,j}^{(n)}</math> est l'indice du premier sommet intermédiaire entre <math>i</math> et <math>j</math>,  le second sommet est donné par <math>d_{p,j}^{(n)}</math> où <math>p=d_{i,j}^{(n)}</math>, etc.

== Applications ==

=== Existence des chemins joignant des sommets ===

C'est le problème de savoir, pour tout couple <math>(x,y)</math> de sommets, s'il existe un chemin de <math>x</math> à <math>y</math>, ou de connaître, pour un sommet <math>s</math> donné, les sommets accessibles à partir de <math>s</math>. 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|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 <math>\oplus=\max</math> et <math>\otimes=\min</math>.

=== Réseaux routiers ===
{{loupe|Recherche de chemin}}
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 [[Graphe orienté|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é {{Citation étrangère|langue=en|Highway Dimension}}<ref>{{article
 |auteur1= Ittai Abraham
 |auteur2= Amos Fiat
 |auteur3= Andrew V. Goldberg
 |auteur4= Renato Fonseca F. Werneck
 |titre= Highway Dimension, Shortest Paths, and Provably Efficient Algorithms
 |journal = ACM-SIAM Symposium on Discrete Algorithms 
 |pages = 782-793
 |année = 2010
 |url= http://research.microsoft.com/pubs/115272/soda10.pdf%20research.microsoft.com/pubs/115272/soda10.pdf}}.
</ref>. 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é {{Citation étrangère|langue=en|hub labelling}}, et calcule les chemins les plus courts en quelques fractions de secondes<ref>{{chapitre
 |auteur1= Ittai Abraham
 |auteur2= Daniel Delling
 |auteur3= Andrew V. Goldberg
 |auteur4 = Renato Fonseca F. Werneck
 | titre = A Hub-Based Labeling Algorithm for Shortest Paths on Road Networks"
 | auteurs ouvrage = Panos M. Pardalos et Steffen Rebennack (éditeurs)
 | titre ouvrage = Experimental Algorithms ''(10th International Symposium on Experimental Algorithms, Kolimpari, Chania, Crète, 5-7 mai 2011)''
 | éditeur = Springer Science & Business Media
 | année = 2011
 | pages totales = 460
 | passage = 230-241
 | isbn = 9783642206610
 | url = http://research.microsoft.com/pubs/142356/HL-TR.pdf%20research.microsoft.com/pubs/142356/HL-TR.pdf
}}.</ref>

=== Plus court chemin pour des poids dynamiques ===

Dans certains problèmes de transport, les poids sont des fonctions qui peuvent varier avec le temps pour tenir compte des fluctuations du trafic par exemple. Dans ce cas, la méthode algébrique s'applique toujours en choisissant comme demi-anneau le demi-anneau des endomorphismes croissants sur un [[dioïde]], avec la somme induite <math>(f \oplus g)(x) = f(x)\oplus g(x)</math>, et la composition pour produit. Ainsi, si l'on cherche à trouver le chemin le plus rapide dans un réseau où le trafic est variable en fonction de l'heure de départ, on peut appliquer les algorithmes usuels en valuant chaque route par une fonction donnant l'heure d'arrivée en fonction de l'heure de départ, et en considérant pour <math>\oplus</math> le minimum d'une fonction prise à l'heure de départ.

=== Plus court chemin avec contraintes temporelles ===

Il arrive, en particulier dans les réseaux de transports en commun, que certains arcs ne puissent être parcourus que dans certaines contraintes horaires (pas la nuit par exemple). On suppose que le temps de parcours de chaque arc <math>(i,j)</math> est fixé, ainsi qu'un ensemble de plages horaires <math>H_{i,j}</math> où il est possible d'emprunter cette route. On considère alors le dioïde des endomorphismes pris sur les intervalles de temps définis ainsi : soit <math>D_{i}</math> l'intervalle de temps où l'on souhaite partir du sommet <math>i</math> ; alors <math>\tau_{i,j}(D_i) = \{d_{i,j} + t | t \in D_i \cap H_{i,j}\}</math> est l'intervalle de temps où il est possible d'arriver au sommet <math>j</math> relié à <math>i</math>. On peut ajouter d'autres contraintes à <math>\tau</math> (par intersection avec des plages horaires pour éviter certaines périodes, en ajoutant des contraintes de prix par [[produit cartésien]] avec la matrice des coûts de transport muni d'une loi min pondérée entre temps et prix). Dans tous les cas, l'[[algorithme de Dijkstra]] permet une résolution efficace.

=== Réseaux stochastiques avec contraintes temporelles ===

Dans des situations réelles, le réseau de transport est habituellement stochastique et dépend du temps. En effet, un voyageur qui parcourt un trajet quotidiennement peut connaître des temps de déplacement différents sur ce trajet en raison non seulement des fluctuations de l'intensité du trafic, mais aussi des incidents plus localisés tels que les zones de travaux sur la chaussée, les mauvaises conditions climatiques, les accidents et les pannes de véhicules. Par conséquent, un réseau stochastique temporel est une représentation plus réaliste d'un réseau routier réel qu'un réseau déterministe<ref>
{{article |nom1=Rajabi-Bahaabadi |prénom1=Mojtaba |prénom2=Afshin |nom2=Shariat-Mohaymany |prénom3=Mohsen |nom3=Babaei |prénom4=Chang Wook |nom4=Ahn |titre=Multi-objective path finding in stochastic time-dependent road networks using non-dominated sorting genetic algorithm |journal=Expert Systems with Applications |date=2015 |volume=42 |numéro=12|pages=5056–5064 |doi=10.1016/j.eswa.2015.02.046 |présentation en ligne=http://www.sciencedirect.com/science/article/pii/S0957417415001530}}.
</ref>. Malgré des progrès considérables, la définition et l'identification d'un chemin optimal dans les réseaux routiers stochastiques reste un sujet controversé. En d'autres termes, il n'y a pas de définition unique d'un chemin optimal en présence d'incertitude. Une réponse possible et répandue est un chemin qui réalise le temps de déplacement minimum prévu. Le principal avantage de cette approche qu'elle permet d'utiliser les algorithmes de plus court chemin introduits pour les réseaux déterministes pour identifier le trajet avec le temps de déplacement minimum attendu dans un réseau stochastique. 

Cependant, le chemin optimal peut ne pas être satisfaisant, parce que cette approche ne prend pas en compte la variabilité du temps de déplacement. Pour résoudre ce problème, certains chercheurs utilisent une distribution du temps de déplacement plutôt que la valeur moyenne,  et ils obtiennent la [[Loi de probabilité|distribution de probabilité]] du temps de déplacement total en utilisant différentes méthodes d'optimisation telles que la [[programmation dynamique]] et l'[[algorithme de Dijkstra]]<ref>
{{article |nom1=Olya |prénom1=Mohammad Hessam |titre=Finding shortest path in a combined exponential – gamma probability distribution arc length |journal=International Journal of Operational Research |date=2014 |volume=21 |numéro=1|pages=25–37 |doi=10.1504/IJOR.2014.064020 |présentation en ligne=http://www.inderscience.com/info/inarticle.php?artid=64020}}.
</ref>. Ces méthodes utilisent l'optimisation stochastique, et notamment la programmation dynamique stochastique pour trouver le chemin le plus court dans les réseaux à [[Longueur d'un arc|longueur d'arc]] probabiliste<ref>
{{article |nom1=Olya |prénom1=Mohammad Hessam |titre=Applying Dijkstra’s algorithm for general shortest path problem with normal probability distribution arc length |journal=International Journal of Operational Research |date=2014 |volume=21 |numéro=2|pages=143–154 |doi=10.1504/IJOR.2014.064541 |présentation en ligne=http://www.inderscienceonline.com/doi/full/10.1504/IJOR.2014.064541}}.
</ref>. 
Il convient de noter que le concept de fiabilité du temps de déplacement est utilisé de façon interchangeable avec la variabilité du temps de déplacement dans la littérature de recherche sur les transports, de sorte que, en général, on peut dire que plus la variabilité du temps de déplacement est élevée, plus la fiabilité est basse et vice-versa.

Afin de rendre compte plus précisément de la fiabilité du temps de déplacement, deux définitions alternatives communes pour un chemin optimal sous incertitude ont été suggérées. Certains ont introduit le concept de chemin le plus fiable, visant à maximiser la probabilité d'arriver à temps ou plus tôt qu'un coût de déplacement donné. D'autres ont mis en avant le concept d'un chemin α-fiable sur la base duquel ils ont eu l'intention de minimiser le coût du déplacement pour assurer une probabilité d'arrivée à l'heure prédéterminée.

== Complexité ==
Mulmulay et Shah ont donné des bornes inférieures de complexité pour le problème du plus court chemin<ref>{{Article|langue=en|titre=A Lower Bound for the Shortest Path Problem|périodique=Journal of Computer and System Sciences|volume=63|numéro=2|date=2001-09-01|issn=0022-0000|doi=10.1006/jcss.2001.1766|lire en ligne=https://www.sciencedirect.com/science/article/pii/S0022000001917660|consulté le=2018-11-08|pages=253–267}}</ref>.

== Notes et références ==
{{Références}}
{{Traduction/Référence|en|Shortest path problem|type=note}}

== Bibliographie ==
;Ouvrages
* {{Ouvrage
| auteur1=Jean Claude Derniame
| auteur2=Claude Pair
| titre=Problèmes de cheminement dans les graphes
| éditeur=Dunod (Paris)
| année=1971
| pages totales=182
}}
* {{Cormen2en}}
*: Section 26.2. « The Floyd-Warshall algorithm », {{p.|558–565}}; 
*: Section 26.4. « A general [[framework]] for solving path problems in directed graphs », {{p.|570–576}}.
* {{Cormen3fr}}
** Chapitre 24. « Plus courts chemins à l’origine unique »
** Chapitre 25. « Plus courts chemins entre toutes paires de sommets »
* {{Ouvrage
 |langue=fr
 |auteur1=Michel Gondran
 |auteur2=Michel Minoux
 |titre=Graphes et algorithmes
 |lieu=Paris
 |éditeur=Lavoisier
 |collection=Études et recherches d'Électricité de France
 |année=2004
 |numéro d'édition=4
 |année première édition=1979
 |pages totales=xxxi+784
 |isbn=978-2-7430-1035-5
}}
*: Chapitre 2. « Le problème du plus court chemin »
*: Chapitre 3. « Algèbres de chemins et dioïdes »
* {{Ouvrage|
langue=en|
auteur1=[[Alexander Schrijver]]|
titre=Combinatorial Optmization|
lieu=Berlin/Heidelberg/New York|
éditeur=Springer|
année=2004|
pages totales=1881|
isbn=3-540-44389-4|
lire en ligne=https://books.google.com/books?id=mqGeSQ6dJycC&printsec=frontcover
}}
*: Chapter 8. « Shortest paths : arbitrary lengths »

;Articles
<!-- 1966 -->
*{{Chapitre
| auteur = Claude Pair
| titre =  Sur des algorithmes pour des problèmes de cheminement dans les graphes finis
| titre ouvrage = Théorie des graphes (journées internationales d'études) -- Theory of Graphs (internainal symposium)
| éditeur = Dunod (Paris) et  Gordon and Breach (New York)
| année = 1966
| adresse = Rome (Italie)
| page début = 271
| auteur ouvrage = P. Rosentiehl
}}
<!-- 1990 -->
*{{article
 |auteur1= Ravindra K. Ahuja 
 |auteur2= [[Kurt Mehlhorn]] 
 |auteur3= James Orlin 
 |auteur4= Robert E. Tarjan 
 |mois = avril
 |année = 1990 
 |titre=Faster algorithms for the shortest path problem |url=http://www.dtic.mil/cgi-bin/GetTRDoc?AD=ADA194031   
 |journal=Journal of the ACM |périodique=ACM |volume=37 |numéro=2 |pages=213–223 
 |doi=10.1145/77600.77615}}.
<!-- 2000 -->
*{{chapitre 
 |url=http://dl.acm.org/citation.cfm?id=686343&CFID=563073233&CFTOKEN=28801665 
 |titre=Improved Shortest Paths on the Word RAM 
 |auteur =Torben Hagerup |année=2000 |isbn=3-540-67715-1 |passage=61–72 
 |auteurs ouvrage = Ugo Montanari, José D. P. Rolim et Emo Welzl (éditeurs)
 |titre ouvrage = Proceedings of the 27th International Colloquium on Automata, Languages and Programming}}.
<!-- 2002 -->
*{{article 
 |url=http://dl.acm.org/citation.cfm?id=545417&CFID=563073233&CFTOKEN=28801665 
 |titre=Computing shortest paths with comparisons and additions 
 |auteur2 = Vijaya Ramachandran 
 |auteur1 = Seth Pettie
 | année=2002
 | isbn=0-89871-513-X
 |pages=267–276
 |journal=Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms}}
<!-- 2004 -->
*{{article
 | auteur = Seth Pettie
 | mois =  janvier
 | année =  2004 
 |titre=A new approach to all-pairs shortest paths on real-weighted graphs 
 |journal=Theoretical Computer Science 
 |volume=312 
 |numéro=1 
 |pages=47–74 
 |doi=10.1016/s0304-3975(03)00402-x}}
<!-- 2004 -->
*{{article
 |nom=Thorup|prénom=Mikkel
 |date=2004
 |titre=Integer priority queues with decrease key in constant time and the single source shortest paths problem
 |url=http://dl.acm.org/citation.cfm?id=1039326
 |journal=Journal of Computer and System Sciences
 |volume=69
 |numéro=3
 |pages=330–353
 |doi=10.1016/j.jcss.2004.04.003}}.
*{{article |nom=Williams |prénom=Ryan 
 |arxiv=1312.6680 
 |titre=Faster all-pairs shortest paths via circuit complexity 
 |doi=10.1145/2591796.2591811 
 |math reviews =3238994 
 |pages=664–673 
 |périodique=ACM |lieu=New York 
 |journal= Proceedings of the 46th Annual ACM Symposium on Theory of Computing ''(STOC '14)'' 
 |année=2014}}.

== Articles liés ==
{{début colonnes | taille = 30}}
* [[Lexique de la théorie des graphes]]
* [[Liste des algorithmes de la théorie des graphes#Algorithmes de plus courts chemins (PCC)| Algorithmes de plus courts chemins]]
* [[Recherche de chemin]]
* [[Algorithme de parcours en largeur]]
* [[Algorithme de Dijkstra]]
* [[Algorithme A*]]
* [[Algorithme de Bellman-Ford]] 
* [[Algorithme de Floyd-Warshall]] 
* [[Algorithme de Warshall]] 
* [[Contractions hiérarchiques]]
* [[IEEE 802.1aq]]
* [[Réseau de flot]]
* [[Plus court chemin euclidien]]
* [[Mathématiques tropicales]]
* [[Algorithme de Johnson]]
* [[Problème de flot maximum]]
* [[Distance (théorie des graphes)]]
{{fin colonnes}}


{{Portail|informatique théorique}}

[[Catégorie:Théorie des graphes]]
[[Catégorie:Problème algorithmique]]
[[Catégorie:Graphe orienté]]