Problème du chemin le plus court

En théorie des graphes , le problème du plus court chemin est le problème de trouver un chemin entre deux sommets (ou nœuds) d'un graphe tel que la somme des poids de ses arêtes constitutives soit minimisée.

Le problème de trouver le chemin le plus court entre deux intersections sur une carte routière peut être modélisé comme un cas particulier du problème du chemin le plus court dans les graphes, où les sommets correspondent aux intersections et les arêtes correspondent aux segments de route, chacun pondéré par la longueur ou la distance de chaque segment.

Définition

Le problème du plus court chemin peut être défini pour les graphes non orientés , orientés ou mixtes . La définition des graphes non orientés stipule que chaque arête peut être parcourue dans les deux sens. Les graphes orientés nécessitent que les sommets consécutifs soient connectés par une arête orientée appropriée.

Deux sommets sont adjacents lorsqu'ils sont tous deux incidents à une arête commune. Un chemin dans un graphe non orienté est une séquence de sommets telle que est adjacente à pour . Un tel chemin est appelé un chemin de longueur de à . (Les sont des variables ; leur numérotation est liée à leur position dans la séquence et n'a pas besoin d'être liée à un étiquetage canonique.) ${\displaystyle P=(v_{1},v_{2},\ldots ,v_{n})\in V imes V imes \cdots imes V <semantics> <mrow> <mstyle> <mi>P</mi> <mo>=</mo> <mo>(</mo> <msub> <mi>v</mi> <mrow> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>v</mi> <mrow> <mn>2</mn> </mrow> </msub> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msub> <mi>v</mi> <mrow> <mi>n</mi> </mrow> </msub> <mo>)</mo> <mo>∈</mo> <mi>V</mi> <mo>×</mo> <mi>V</mi> <mo>×</mo> <mo>⋯</mo> <mo>×</mo> <mi>V</mi> </mstyle> </mrow> <annotation>{\displaystyle P=(v_{1},v_{2},\ldots ,v_{n})\dans V\fois V\fois \cdots \fois V}</annotation> </semantics> </math><img src=$ ${\displaystyle v_{i <semantics> <mrow> <mstyle> <msub> <mi>v</mi> <mrow> <mi>je</mi> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle v_{i}}</annotation> </semantics> </math><img src=$ ${\displaystyle v_{i+1 <semantics> <mrow> <mstyle> <msub> <mi>v</mi> <mrow> <mi>je</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle v_{i+1}}</annotation> </semantics> </math><img src=$ ${\displaystyle 1\leq i<n <semantics> <mrow> <mstyle> <mn>1</mn> <mo>≤</mo> <mi>je</mi> <mo><</mo> <mi>n</mi> </mstyle> </mrow> <annotation>{\displaystyle 1\leq i<n}</annotation> </semantics> </math><img src=$ ${\displaystyle P <semantics> <mrow> <mstyle> <mi>P</mi> </mstyle> </mrow> <annotation>{\displaystyle P}</annotation> </semantics> </math><img src=$ ${\displaystyle n-1 <semantics> <mrow> <mstyle> <mi>n</mi> <mo>−</mo> <mn>1</mn> </mstyle> </mrow> <annotation>{\displaystyle n-1}</annotation> </semantics> </math><img src=$ ${\displaystyle v_{1 <semantics> <mrow> <mstyle> <msub> <mi>v</mi> <mrow> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle v_{1}}</annotation> </semantics> </math><img src=$ ${\displaystyle v_{n <semantics> <mrow> <mstyle> <msub> <mi>v</mi> <mrow> <mi>n</mi> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle v_{n}}</annotation> </semantics> </math><img src=$ ${\displaystyle v_{i <semantics> <mrow> <mstyle> <msub> <mi>v</mi> <mrow> <mi>je</mi> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle v_{i}}</annotation> </semantics> </math><img src=$

Soit où est l'arête incidente à la fois à et à . Étant donné une fonction de pondération à valeur réelle et un graphe non orienté (simple) , le chemin le plus court de à est le chemin (où et ) qui minimise globalement la somme Lorsque chaque arête du graphe a un poids unitaire ou , cela équivaut à trouver le chemin avec le moins d'arêtes. ${\displaystyle E=\{e_{i,j}\ <semantics> <mrow> <mstyle> <mi>E</mi> <mo>=</mo> <mo>{</mo> <msub> <mi>et</mi> <mrow> <mi>je</mi> <mo>,</mo> <mi>j</mi> </mrow> </msub> <mo>}</mo> </mstyle> </mrow> <annotation>{\displaystyle E=\{e_{i,j}\}}</annotation> </semantics> </math><img src=$ ${\displaystyle e_{i,j <semantics> <mrow> <mstyle> <msub> <mi>et</mi> <mrow> <mi>je</mi> <mo>,</mo> <mi>j</mi> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle e_{i,j}}</annotation> </semantics> </math><img src=$ ${\displaystyle v_{i <semantics> <mrow> <mstyle> <msub> <mi>v</mi> <mrow> <mi>je</mi> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle v_{i}}</annotation> </semantics> </math><img src=$ ${\displaystyle v_{j <semantics> <mrow> <mstyle> <msub> <mi>v</mi> <mrow> <mi>j</mi> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle v_{j}}</annotation> </semantics> </math><img src=$ ${\displaystyle f:E ightarrow \mathbb {R} <semantics> <mrow> <mstyle> <mi>f</mi> <mo>:</mo> <mi>E</mi> <mo>→</mo> <mrow> <mi>R</mi> </mrow> </mstyle> </mrow> <annotation>{\displaystyle f:E ightarrow \mathbb {R} }</annotation> </semantics> </math><img src=$ ${\displaystyle G <semantics> <mrow> <mstyle> <mi>G</mi> </mstyle> </mrow> <annotation>{\displaystyle G}</annotation> </semantics> </math><img src=$ ${\displaystyle v <semantics> <mrow> <mstyle> <mi>v</mi> </mstyle> </mrow> <annotation>{\displaystyle v}</annotation> </semantics> </math><img src=$ ${\displaystyle v' <semantics> <mrow> <mstyle> <msup> <mi>v</mi> <mo>′</mo> </msup> </mstyle> </mrow> <annotation>{\displaystyle v'}</annotation> </semantics> </math><img src=$ ${\displaystyle P=(v_{1},v_{2},\ldots ,v_{n}) <semantics> <mrow> <mstyle> <mi>P</mi> <mo>=</mo> <mo>(</mo> <msub> <mi>v</mi> <mrow> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>v</mi> <mrow> <mn>2</mn> </mrow> </msub> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msub> <mi>v</mi> <mrow> <mi>n</mi> </mrow> </msub> <mo>)</mo> </mstyle> </mrow> <annotation>{ displaystyle P = (v_ {1}, v_ {2}, \ ldots, v_ {n})}</annotation> </semantics> </math><img src=$ ${\displaystyle v_{1}=v <semantics> <mrow> <mstyle> <msub> <mi>v</mi> <mrow> <mn>1</mn> </mrow> </msub> <mo>=</mo> <mi>v</mi> </mstyle> </mrow> <annotation>{\displaystyle v_{1}=v}</annotation> </semantics> </math><img src=$ ${\displaystyle v_{n}=v' <semantics> <mrow> <mstyle> <msub> <mi>v</mi> <mrow> <mi>n</mi> </mrow> </msub> <mo>=</mo> <msup> <mi>v</mi> <mo>′</mo> </msup> </mstyle> </mrow> <annotation>{\displaystyle v_{n}=v'}</annotation> </semantics> </math><img src=$ ${\displaystyle n <semantics> <mrow> <mstyle> <mi>n</mi> </mstyle> </mrow> <annotation>{\displaystyle n}</annotation> </semantics> </math><img src=$ ${\displaystyle \sum _{i=1}^{n-1}f(e_{i,i+1}). <semantics> <mrow> <mstyle> <munderover> <mo>∑</mo> <mrow> <mi>je</mi> <mo>=</mo> <mn>1</mn> </mrow> <mrow> <mi>n</mi> <mo>−</mo> <mn>1</mn> </mrow> </munderover> <mi>f</mi> <mo>(</mo> <msub> <mi>et</mi> <mrow> <mi>je</mi> <mo>,</mo> <mi>je</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> <mo>)</mo> <mo>.</mo> </mstyle> </mrow> <annotation>{\displaystyle \sum _{i=1}^{n-1}f(e_{i,i+1}).}</annotation> </semantics> </math><img src=$ ${\displaystyle f:E ightarrow \{1\ <semantics> <mrow> <mstyle> <mi>f</mi> <mo>:</mo> <mi>E</mi> <mo>→</mo> <mo>{</mo> <mn>1</mn> <mo>}</mo> </mstyle> </mrow> <annotation>{ displaystyle f: E rightarrow {1}}</annotation> </semantics> </math><img src=$

Le problème est également parfois appelé problème du plus court chemin à paire unique , pour le distinguer des variantes suivantes :

Le problème du plus court chemin à source unique , dans lequel nous devons trouver les chemins les plus courts d'un sommet source v vers tous les autres sommets du graphe.
Le problème du chemin le plus court à destination unique , dans lequel nous devons trouver les chemins les plus courts à partir de tous les sommets du graphe orienté vers un seul sommet de destination v . Cela peut être réduit au problème du chemin le plus court à source unique en inversant les arcs dans le graphe orienté.
Le problème du chemin le plus court entre toutes les paires , dans lequel nous devons trouver les chemins les plus courts entre chaque paire de sommets v , v' dans le graphe.

Ces généralisations ont des algorithmes nettement plus efficaces que l’approche simpliste consistant à exécuter un algorithme de chemin le plus court à paire unique sur toutes les paires de sommets pertinentes.

Algorithmes

Il existe plusieurs algorithmes bien connus pour résoudre ce problème et ses variantes.

L'algorithme de Dijkstra résout le problème du chemin le plus court à source unique avec uniquement des poids de bord non négatifs.
L'algorithme de Bellman-Ford résout le problème de source unique si les poids des bords peuvent être négatifs.
Un algorithme de recherche* résout le chemin le plus court à paire unique en utilisant des heuristiques pour tenter d'accélérer la recherche.
L'algorithme de Floyd-Warshall résout toutes les paires de chemins les plus courts.
L'algorithme de Johnson résout toutes les paires de chemins les plus courts et peut être plus rapide que Floyd-Warshall sur des graphes clairsemés .
L'algorithme de Viterbi résout le problème du chemin stochastique le plus court avec un poids probabiliste supplémentaire sur chaque nœud.

Des algorithmes supplémentaires et des évaluations associées peuvent être trouvés dans Cherkassky, Goldberg et Radzik (1996).

Chemins les plus courts à source unique

Graphes non orientés

Graphiques non pondérés

Graphes acycliques orientés

Un algorithme utilisant le tri topologique peut résoudre le problème du chemin le plus court à source unique en temps Θ( E + V ) dans des graphes acycliques dirigés à pondération arbitraire.

Graphes orientés avec des poids non négatifs

Le tableau suivant est tiré de Schrijver (2004), avec quelques corrections et ajouts. Un fond vert indique une borne asymptotiquement optimale dans le tableau ; L est la longueur (ou le poids) maximum parmi toutes les arêtes, en supposant des poids d'arêtes entiers.

Graphes dirigés avec des poids arbitraires sans cycles négatifs

Graphes dirigés avec des poids arbitraires avec des cycles négatifs

Trouve un cycle négatif ou calcule les distances vers tous les sommets.

Graphes planaires avec poids non négatifs

Applications

Les flux de réseau sont un concept fondamental de la théorie des graphes et de la recherche opérationnelle, souvent utilisé pour modéliser des problèmes impliquant le transport de marchandises, de liquides ou d'informations à travers un réseau. Un problème de flux de réseau implique généralement un graphe orienté où chaque arête représente un tuyau, un fil ou une route, et chaque arête a une capacité, qui est la quantité maximale qui peut s'écouler à travers elle. L'objectif est de trouver un flux réalisable qui maximise le flux d'un nœud source à un nœud récepteur.

Les problèmes de chemin le plus court peuvent être utilisés pour résoudre certains problèmes de flux de réseau, en particulier lorsqu'il s'agit de réseaux à source unique et à récepteur unique. Dans ces scénarios, nous pouvons transformer le problème de flux de réseau en une série de problèmes de chemin le plus court.

Étapes de la transformation

Créer un graphique résiduel :
- Pour chaque arête (u, v) du graphe d'origine, créez deux arêtes dans le graphe résiduel :
  - (u, v) avec capacité c(u, v)
  - (v, u) avec une capacité de 0
- Le graphique résiduel représente la capacité restante disponible dans le réseau.
Trouver le chemin le plus court :
- Utilisez un algorithme de chemin le plus court (par exemple, l'algorithme de Dijkstra, l'algorithme de Bellman-Ford) pour trouver le chemin le plus court du nœud source au nœud récepteur dans le graphe résiduel.
Augmenter le flux :
- Trouvez la capacité minimale le long du chemin le plus court.
- Augmenter le débit sur les bords du chemin le plus court de cette capacité minimale.
- Diminuer la capacité des bords dans le sens avant et augmenter la capacité des bords dans le sens arrière.
Mettre à jour le graphique résiduel :
- Mettre à jour le graphique résiduel en fonction du flux augmenté.
Répéter:
- Répétez les étapes 2 à 4 jusqu’à ce qu’aucun autre chemin ne puisse être trouvé entre la source et le récepteur.

Chemins les plus courts pour toutes les paires

Le problème du chemin le plus court entre toutes les paires de sommets v , v' du graphe permet de trouver les chemins les plus courts entre chaque paire de sommets v , v' du graphe . Le problème du chemin le plus court entre toutes les paires de sommets pour les graphes orientés non pondérés a été introduit par Shimbel (1953), qui a observé qu'il pouvait être résolu par un nombre linéaire de multiplications de matrices qui prend un temps total de O ( V ⁴ ) .

Graphe non orienté

Graphe orienté

Applications

Les algorithmes de chemin le plus court sont utilisés pour trouver automatiquement des directions entre des emplacements physiques, comme les itinéraires routiers sur des sites Web de cartographie Web comme MapQuest ou Google Maps . Pour cette application, des algorithmes spécialisés rapides sont disponibles.

Si l'on représente une machine abstraite non déterministe sous la forme d'un graphe dans lequel les sommets décrivent les états et les arêtes les transitions possibles, les algorithmes du chemin le plus court peuvent être utilisés pour trouver une séquence optimale de choix pour atteindre un certain état final, ou pour établir des bornes inférieures sur le temps nécessaire pour atteindre un état donné. Par exemple, si les sommets représentent les états d'un puzzle comme un Rubik's Cube et que chaque arête orientée correspond à un seul mouvement ou à un seul tour, les algorithmes du chemin le plus court peuvent être utilisés pour trouver une solution qui utilise le nombre minimum de mouvements possible.

Dans un esprit de réseau ou de télécommunication , ce problème de chemin le plus court est parfois appelé problème de chemin à délai minimal et généralement associé à un problème de chemin le plus large . Par exemple, l'algorithme peut rechercher le chemin le plus court (délai minimal) le plus large ou le chemin le plus court (délai minimal) le plus large.

Une application plus légère est celle des jeux des « six degrés de séparation » qui tentent de trouver le chemin le plus court dans des graphiques comme des stars de cinéma apparaissant dans le même film.

D'autres applications, souvent étudiées dans la recherche opérationnelle , comprennent l'aménagement d'usines et d'installations, la robotique , le transport et la conception VLSI .

Réseaux routiers

Un réseau routier peut être considéré comme un graphe à poids positifs. Les nœuds représentent des carrefours routiers et chaque arête du graphe est associée à un segment de route entre deux carrefours. Le poids d'une arête peut correspondre à la longueur du segment de route associé, au temps nécessaire pour parcourir le segment ou au coût de la traversée du segment. En utilisant des arêtes dirigées, il est également possible de modéliser des rues à sens unique. De tels graphes sont particuliers dans le sens où certaines arêtes sont plus importantes que d'autres pour les déplacements longue distance (par exemple les autoroutes). Cette propriété a été formalisée en utilisant la notion de dimension d'autoroute. Il existe un grand nombre d'algorithmes qui exploitent cette propriété et sont donc capables de calculer le chemin le plus court beaucoup plus rapidement que ce qui serait possible sur des graphes généraux.

Tous ces algorithmes fonctionnent en deux phases. Dans la première phase, le graphe est prétraité sans connaître le nœud source ou cible. La deuxième phase est la phase de requête. Dans cette phase, le nœud source et le nœud cible sont connus. L'idée est que le réseau routier est statique, donc la phase de prétraitement peut être effectuée une fois et utilisée pour un grand nombre de requêtes sur le même réseau routier.

L'algorithme avec le temps de requête le plus rapide connu est appelé étiquetage des hubs et est capable de calculer le chemin le plus court sur les réseaux routiers d'Europe ou des États-Unis en une fraction de microseconde. D'autres techniques qui ont été utilisées sont :

ALT ( recherche A* , points de repère et inégalité triangulaire )
Drapeaux d'arc
Hiérarchies de contraction
Routage des nœuds de transit
Élagage basé sur la portée
Étiquetage
Étiquettes de hub

Problèmes connexes

Pour les problèmes de plus court chemin en géométrie computationnelle , voir Plus court chemin euclidien .

Le chemin multiple déconnecté le plus court est une représentation du réseau de chemins primitifs dans le cadre de la théorie de la reptation . Le problème du chemin le plus large cherche un chemin tel que l'étiquette minimale de chaque arête soit aussi grande que possible.

D’autres problèmes connexes peuvent être classés dans les catégories suivantes.

Chemins avec contraintes

Contrairement au problème du chemin le plus court, qui peut être résolu en temps polynomial dans des graphes sans cycles négatifs, les problèmes de chemin le plus court qui incluent des contraintes supplémentaires sur le chemin de solution souhaité sont appelés Constrained Shortest Path First et sont plus difficiles à résoudre. Un exemple est le problème du chemin le plus court contraint, qui tente de minimiser le coût total du chemin tout en maintenant en même temps une autre métrique en dessous d'un seuil donné. Cela rend le problème NP-complet (on pense que de tels problèmes ne sont pas efficacement résolubles pour de grands ensembles de données, voir le problème P = NP ). Un autre exemple NP-complet nécessite qu'un ensemble spécifique de sommets soit inclus dans le chemin, ce qui rend le problème similaire au problème du voyageur de commerce (TSP). Le TSP est le problème de trouver le chemin le plus court qui passe par chaque sommet exactement une fois et revient au début. Le problème de trouver le chemin le plus long dans un graphe est également NP-complet.

Observabilité partielle

Le problème du voyageur canadien et le problème du plus court chemin stochastique sont des généralisations où le graphique n'est pas complètement connu du voyageur, change au fil du temps ou où les actions (traversées) sont probabilistes.

Les chemins les plus courts stratégiques

Parfois, les arêtes d'un graphe ont des personnalités : chacune d'elles a son propre intérêt égoïste. Un exemple est un réseau de communication, dans lequel chaque arête est un ordinateur qui appartient éventuellement à une personne différente. Différents ordinateurs ont des vitesses de transmission différentes, donc chaque arête du réseau a un poids numérique égal au nombre de millisecondes nécessaires à la transmission d'un message. Notre objectif est d'envoyer un message entre deux points du réseau dans le temps le plus court possible. Si nous connaissons le temps de transmission de chaque ordinateur (le poids de chaque arête), nous pouvons alors utiliser un algorithme standard des chemins les plus courts. Si nous ne connaissons pas les temps de transmission, nous devons alors demander à chaque ordinateur de nous indiquer son temps de transmission. Mais les ordinateurs peuvent être égoïstes : un ordinateur peut nous dire que son temps de transmission est très long, afin que nous ne l'ennuyions pas avec nos messages. Une solution possible à ce problème est d'utiliser une variante du mécanisme VCG , qui incite les ordinateurs à révéler leur véritable poids.

Détection de cycle négatif

Dans certains cas, l'objectif principal n'est pas de trouver le chemin le plus court, mais seulement de détecter si le graphique contient un cycle négatif. Certains algorithmes de chemins les plus courts peuvent être utilisés à cette fin :

L’ algorithme de Bellman-Ford peut être utilisé pour détecter un cycle négatif dans le temps . ${\displaystyle O(|V||E|) <semantics> <mrow> <mstyle> <mi>O</mi> <mo>(</mo> <mrow> <mo>|</mo> </mrow> <mi>V</mi> <mrow> <mo>|</mo> </mrow> <mrow> <mo>|</mo> </mrow> <mi>E</mi> <mrow> <mo>|</mo> </mrow> <mo>)</mo> </mstyle> </mrow> <annotation>{\displaystyle O(|V||E|)}</annotation> </semantics> </math><img src=$
Cherkassky et Goldberg examinent plusieurs autres algorithmes de détection de cycles négatifs.

Cadre algébrique général sur les demi-anneaux : le problème du chemin algébrique

De nombreux problèmes peuvent être formulés comme une forme de chemin le plus court pour certaines notions convenablement substituées d'addition le long d'un chemin et de prise du minimum. L'approche générale consiste à considérer les deux opérations comme celles d'un demi-anneau . La multiplication des demi-anneaux est effectuée le long du chemin et l'addition se fait entre les chemins. Ce cadre général est connu sous le nom de problème du chemin algébrique .

La plupart des algorithmes classiques du plus court chemin (et des nouveaux) peuvent être formulés comme résolvant des systèmes linéaires sur de telles structures algébriques.

Plus récemment, un cadre encore plus général pour résoudre ces problèmes (et des problèmes beaucoup moins évidemment liés) a été développé sous la bannière des algèbres de valorisation .

Chemin le plus court dans les réseaux stochastiques dépendants du temps

Dans la réalité, un réseau de transport est généralement stochastique et dépendant du temps. La durée du trajet sur un segment de route dépend de nombreux facteurs tels que le volume de trafic (matrice origine-destination), les travaux routiers, la météo, les accidents et les pannes de véhicules. Un modèle plus réaliste d'un tel réseau routier est un réseau stochastique dépendant du temps (STD).

Il n'existe pas de définition acceptée du chemin optimal dans des conditions d'incertitude (c'est-à-dire dans les réseaux routiers stochastiques). Il s'agit d'un sujet controversé, malgré des progrès considérables au cours de la dernière décennie. Une définition courante est un chemin avec le temps de trajet prévu minimum. Le principal avantage de cette approche est qu'elle peut utiliser des algorithmes efficaces de chemin le plus court pour les réseaux déterministes. Cependant, le chemin optimal qui en résulte peut ne pas être fiable, car cette approche ne tient pas compte de la variabilité du temps de trajet.

Pour résoudre ce problème, certains chercheurs utilisent la distribution de la durée du trajet au lieu de sa valeur attendue. Ils trouvent ainsi la distribution de probabilité de la durée totale du trajet en utilisant différentes méthodes d'optimisation telles que la programmation dynamique et l'algorithme de Dijkstra . Ces méthodes utilisent l'optimisation stochastique , en particulier la programmation dynamique stochastique pour trouver le chemin le plus court dans les réseaux avec une longueur d'arc probabiliste. Les termes fiabilité du temps de trajet et variabilité du temps de trajet sont utilisés comme opposés dans la littérature de recherche sur les transports : plus la variabilité est élevée, plus la fiabilité des prévisions est faible.

Pour tenir compte de la variabilité, les chercheurs ont proposé deux définitions alternatives pour un chemin optimal dans des conditions d'incertitude. Le chemin le plus fiable est celui qui maximise la probabilité d'arriver à l'heure compte tenu d'un budget de temps de trajet. Un chemin α-fiable est celui qui minimise le budget de temps de trajet nécessaire pour arriver à l'heure avec une probabilité donnée.