Problème de plus court chemin

On fixe un sommet ${\displaystyle s}$, 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.

On cherche un plus court chemin, ou au moins la longueur d'un tel chemin, pour tous les couples ${\displaystyle (s,t)}$ de sommets.

• L'algorithme de Floyd-Warshall donne la matrice des longueurs des plus courts chemins en temps ${\displaystyle O(n^{3})}$ pour un graphe à ${\displaystyle n}$ 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.

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

Le poids d'un chemin ${\displaystyle c=(i_{0},i_{1},\ldots ,i_{d})}$ est le produit, dans le demi-anneau, des poids de arcs qui le composent :

${\displaystyle w(c)=w(i_{0},i_{1})\otimes w(i_{1},i_{2})\otimes w(i_{d-1},i_{d})}$.

La longueur du plus court chemin de ${\displaystyle i}$ à ${\displaystyle j}$ est, dans ce formalisme la somme des poids de ${\displaystyle i}$ à ${\displaystyle j}$. Si l'on note ${\displaystyle \Gamma _{i,j}}$ l'ensemble des chemins de ${\displaystyle i}$ à ${\displaystyle j}$, le chemin cherché est un chemin dont le poids est

${\displaystyle \bigoplus _{c\in \Gamma _{i,j}}w(c)}$.

Dans le cas où ${\displaystyle \oplus =\min }$ et ${\displaystyle \otimes =+}$, c'est le poids minimal d'un chemin reliant ${\displaystyle i}$ à ${\displaystyle j}$.

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

• une suite de matrices ${\displaystyle A^{(k)}}$ par :

${\displaystyle A^{(0)}=A}$ et

${\displaystyle A^{(k)}=\left(a_{i,j}^{(k)}\right)}$ avec ${\displaystyle a_{i,j}^{(k)}=a_{i,j}^{(k-1)}\oplus \left(a_{i,k}^{(k-1)}\otimes a_{k,j}^{(k-1)}\right)}$.

Cette suite de matrices est telle que l'élément ${\displaystyle a_{i,j}^{(n)}}$ de la matrice ${\displaystyle A^{(n)}}$ est égal à la somme des poids des chemins de longueur au plus ${\displaystyle n}$ de ${\displaystyle i}$ à ${\displaystyle j}$.

• une autre suite de matrices ${\displaystyle D^{(k)}}$ par :

${\displaystyle d_{i,j}^{(0)}={\begin{cases}j&{\text{si }}(i,j){\text{ est un arc}}\\0&{\text{sinon }}\end{cases}}}$

${\displaystyle 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}}.}$

Cette suite de matrices est telle que les éléments ${\displaystyle d_{i,j}^{(k)}}$ ont pour valeur l'indice du premier point intermédiaire du chemin de ${\displaystyle i}$ à ${\displaystyle j}$ à l'étape ${\displaystyle k}$.

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

C'est le problème de savoir, pour tout couple ${\displaystyle (x,y)}$ de sommets, s'il existe un chemin de ${\displaystyle x}$ à ${\displaystyle y}$, ou de connaître, pour un sommet ${\displaystyle s}$ donné, les sommets accessibles à partir de ${\displaystyle s}$. 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.

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.

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 ${\displaystyle \oplus =\max }$ et ${\displaystyle \otimes =\min }$.

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é « Highway Dimension »[6]. 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é « hub labelling », et calcule les chemins les plus courts en quelques fractions de secondes[7]

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 ${\displaystyle (f\oplus g)(x)=f(x)\oplus g(x)}$, 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 ${\displaystyle \oplus }$ le minimum d'une fonction prise à l'heure de départ.

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 ${\displaystyle (i,j)}$ est fixé, ainsi qu'un ensemble de plages horaires ${\displaystyle H_{i,j}}$ 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 ${\displaystyle D_{i}}$ l'intervalle de temps où l'on souhaite partir du sommet ${\displaystyle i}$ ; alors ${\displaystyle \tau _{i,j}(D_{i})=\{d_{i,j}+t|t\in D_{i}\cap H_{i,j}\}}$ est l'intervalle de temps où il est possible d'arriver au sommet ${\displaystyle j}$ relié à ${\displaystyle i}$. On peut ajouter d'autres contraintes à ${\displaystyle \tau }$ (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.

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[8]. 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 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[9]. 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'arc probabiliste[10]. 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.