Le plus court chemin  

Il est courant, lorsque l'on cherche à se rendre d'un point à un autre dans un réseau (routier, par exemple), de chercher le plus court chemin, c'est-à-dire celui dont la distance est la plus petite. Si le nombre de trajets possibles entre le point de départ et le point d'arrivée est faible, il suffira de calculer les longueurs de chacun des trajets - en additionnant la longueur des liens qui le composent - et de comparer directement les longueurs obtenues. Mais une telle solution exhaustive devient rapidement impraticable si le nombre de trajets possibles est grand.
Heureusement, il existe des algorithmes qui évitent d'avoir à calculer tous les trajets possibles. Pour cela, ils mettent en œuvre diverses stratégies.

1. Un problème moins simple qu'il n'y paraît

Un problème vite inextricable

On représente un réseau par un graphe composé de nœuds (les sommets du graphe) et de liens orientés (les arcs du graphe). Imaginez, par exemple, un réseau composé de 20 nœuds - ce qui est très raisonnable - et comportant un lien direct entre chaque nœud (soit 380 liens orientés). Un simple calcul combinatoire montre qu'entre deux nœuds donnés, le nombre de « chemins » possibles est supérieur à 6000 milliards  ! Ainsi, à supposer qu'il faille 1 micro-seconde pour calculer la longueur d'un trajet, la solution exhaustive prendrait environ 6 milliards de secondes, c'est-à-dire plus de 740 000 jours... et même si on réduisait le temps de calcul d'un trajet à 1 nano-seconde, il faudrait encore 741 jours. Cet exemple est extrême, mais il montre bien la nécessité de disposer d'algorithmes évitant de calculer tous les trajets possibles, pour éviter l'« explosion combinatoire ». Heureusement, on connaît de tels algorithmes, dont les temps de calculs resteront proportionnels, dans le pire des cas, au cube du nombre de nœuds (et souvent au carré). Ainsi, pour notre exemple, le nombre de chemins calculés sera au pire de 20³ c'est à dire 8000 ou même de 20² c'est-à-dire 400, selon les cas. Ce qui est nettement mieux, chacun en conviendra.

Un cas particulier d'un problème plus général

Le problème sous-jacent est celui du « chemin de valeur optimale (ou de meilleure valeur) dans un graphe valué ». L'exemple le plus connu est sans doute celui du réseau de communication : il est composé de nœuds et de liens, en général orientés, chaque lien reliant directement un nœud origine à un nœud extrémité. On imagine aisément la diversité du type de valeurs pouvant être attribuées aux liens : distances, temps (de parcours), coûts (de transferts), fiabilités (valeurs comprises entre 0 et 1), capacités (débits maxima, par exemple en kb/s), etc. Le long d'un chemin, les distances, temps, coûts vont en général s'additionner, les fiabilités vont se multiplier, les capacités vont se composer par minimum, et l'on aura tendance à rechercher un minimum dans le cas des distances, temps, coûts, mais un maximum dans le cas des fiabilités ou des capacités.

On imagine aisément toutes les applications d'un tel mécanisme : étude d'un itinéraire routier, organisation d'un réseau de télécommunication, système d'information de trafic d'un réseau ferroviaire, analyse de réseaux sémantiques (par exemple de citations bibliographiques), etc.

L'étude de ce problème générique nécessite une présentation formelle qui fait appel à des notions algébriques avancées . Nous avons choisi de nous limiter ici au problème de recherche du « plus court chemin », que nous préférons appeler « chemin de valeur additive minimale » .

Mieux formaliser le problème pour le résoudre plus efficacement

Précisons maintenant le problème. Nous en distinguons trois types :

1. plus court chemin entre deux sommets donnés;
2. plus courts chemins d'origine fixée mais vers n'importe quelle extrémité ;
3. plus courts chemins de n'importe quelle origine vers n'importe quelle extrémité.

À première vue, il semble que ces problèmes aillent du plus simple au plus complexe. En effet, le nombre de chemins à déterminer augmente. Cependant, et contrairement à l'intuition précédente, la résolution du problème (1) nécessite en général de résoudre le problème (2) ! De plus, dans le cas général, où les valeurs des liens peuvent être négatives, le meilleur algorithme connu pour résoudre le problème (3) ne demande pas plus d'opérations que le meilleur algorithme connu du problème (2). C'est pourquoi nous nous focaliserons sur cet algorithme, celui de Roy-Warshall-Floyd.

Il convient de préciser aussi ce que l'on cherche à déterminer : le premier résultat cherché est bien sûr la valeur minimale (pour chaque couple de sommets considéré).

Meilleur chemin de A à H.

Par exemple, dans le graphe représenté sur cette figure, le meilleur chemin pour aller de A à H a pour valeur 17. Mais souvent cela ne suffit pas : s'il est bien de connaître la meilleure valeur possible, il est encore mieux de connaître le tracé d'un chemin ayant cette valeur. Ainsi, le meilleur chemin de A à H a pour valeur 17, et son tracé est A;C;D;F;G;H. On parle alors de routage.

Le problème étant ainsi précisé, peut-on affirmer qu'il y a toujours une solution ? La question peut paraître triviale, mais elle ne l'est pas. Supposons que les valeurs des arcs soient de signe quelconque, et que ces valeurs s'additionnent le long des chemins. Si le graphe possède des circuits, c'est-à-dire des chemins permettant de revenir au point de départ, il peut exister des chemins empruntant de tels circuits.

Graphe avec circuit absorbant.

Sur cette figure, par exemple, le chemin A;B;D;C;E;D;F;G;H comprend le circuit D;C;E;D. Dans cet exemple, le circuit D;C;E;D a pour valeur -2, qui est <0. Si l'on cherche les chemins de valeur minimale entre A et H, le problème n'a pas de solution. En effet, le chemin A;B;D;F;G;H vaut 19. Le chemin A;B;D;C;E;D;F;G;H est meilleur (valeur 17). Le chemin A;B;D;C;E;D;C;E;D;F;G;H, faisant deux tours, est encore meilleur (valeur 15). Et ainsi de suite : on peut trouver un chemin de valeur aussi petite que l'on veut, en « tournant » suffisamment de fois sur le circuit ! De tels circuits s'appellent circuits absorbants, et leur présence éventuelle doit être détectée par les algorithmes, qui sinon risqueraient de « boucler » indéfiniment. La question n'est pas seulement théorique, car il existe des applications concrètes où les graphes peuvent avoir des circuits dont la valeur est de signe quelconque. C'est le cas par exemple pour les problèmes d'ordonnancement (ou plannings), qui nécessitent le calcul de chemins de valeur maximale.

Différentes stratégies algorithmiques

Si on s'intéresse uniquement à trouver le meilleur chemin issu d'un sommet donné, il existe des algorithmes assez simples et répandus dans lesquels, par construction, il ne peut pas y avoir de circuits absorbants.

L'algorithme ordinal repose sur le principe très simple d'exploration à partir des prédécesseurs, en supposant qu'il n'y a pas de circuit, et que le sommet de départ est le seul sommet sans prédécesseur.

L'algorithme de Dijkstra quant à lui repose sur le principe d'« exploration à partir du meilleur », c'est à dire du meilleur prédécesseur visité. Il peut être utilisé quand tous les arcs ont une valeur non négative, correspondant à ce qui est consommé sur un trajet donné. Dans ce cas, il ne peut pas y avoir de circuits absorbants, mais il peut y avoir d'autres types de circuits, comme des liens bi-directionnels. En pratique, cet algorithme est très souvent utilisé pour résoudre des problèmes de routage dans les réseaux de télécommunication.

Ces deux algorithmes peuvent se substituer à un algorithme plus général, l'algorithme de Bellman-Kalaba (connu aussi comme Bellman-Ford). Cet algorithme ne présuppose pas l'absence de circuits absorbants sur le graphe, et peut détecter et signaler ces circuits éventuels. Il s'appuie sur un des principaux principes d'optimisation combinatoire : le principe de la programmation dynamique, formulé à l'origine par Bellman et Kalaba.

Ces trois mécanismes peuvent être considérés comme des algorithmes d'exploration de la descendance du sommet, avec des stratégies différentes : tous les prédécesseurs calculés pour l'algorithme ordinal ; le meilleur visité, pour celui de Dijkstra ; et enfin par longueur successive pour celui de Bellman-Kalaba.

Les deux premiers ont une complexité plus faible (de l'ordre de n² dans le pire cas) au lieu d'être de l'ordre de n³ pour le dernier, tout comme pour l'algorithme de Roy-Warshall-Floyd. Ils sont donc utiles dans des situations où il y a un très grand nombre de sommets. C'est le cas par exemple des grands réseaux, des réseaux sémantiques (moteurs de recherche), ou encore des systèmes de recherche d'horaires. Ainsi, un graphe modélisant le système horaire des chemins de fer allemands comprend de l'ordre de 1 million de sommets et 1 million et demi d'arcs.

De plus, pour l'algorithme ordinal ou celui de Dijkstra, chaque étape nous fournit la valeur définitive d'un sommet, et on le sait. Si on s'intéresse aux chemins de valeur minimale entre le sommet de départ A et un sommet particulier B, on peut arrêter le calcul dès que B est calculé, même si tous les sommets ne sont pas calculés. On dit que la stratégie est gloutonne, ce qui signifie que certains résultats ne seront plus remis en question (un glouton est quelqu'un qui avale et ne peut pas revenir en arrière, c'est-à-dire ne peut pas remettre en cause ce qu'il vient de faire).

Pour l'algorithme de Bellman-Kalaba ou celui de Roy-Warshall-Floyd, en revanche, aucun sommet ne peut être considéré comme calculé avant que tous les sommets soient calculés : jusqu'à la fin de l'exécution (c'est-à-dire jusqu'à ce que la stabilité soit atteinte), toute valeur est susceptible d'être modifiée. Il s'agit là d'une stratégie de point fixe. Ce sont deux stratégies algorithmiques très générales que l'on rencontre ici.