Le plus court chemin

Aller d'un point à un autre au moindre coût — et découvrir qu'une route de plus peut tout ralentir.

Un réseau : des carrefours reliés par des tronçons, chacun portant un coût — kilomètres, minutes, péage, consommation. Il faut aller d'un point à un autre en minimisant la somme. C'est sans doute le problème d'optimisation le plus exécuté au monde : chaque calcul d'itinéraire, chaque paquet routé sur Internet, chaque robot qui traverse un entrepôt le résout, des milliards de fois par jour.

Sa solution repose sur une propriété d'apparence anodine : tout sous-chemin d'un plus court chemin est lui-même un plus court chemin. Si le meilleur trajet de Paris à Rome passe par Lyon, alors sa portion Paris-Lyon est le meilleur trajet de Paris à Lyon — sinon on la remplacerait. Toute la famille des algorithmes découle de là. Les quatre premières planches les construisent ; la cinquième montre qu'ajouter une route à un réseau peut allonger le trajet de tout le monde.

1Dijkstra : la tache d'huile

L'algorithme de Dijkstra (1956) procède par vagues. Chaque sommet porte une étiquette provisoire — la meilleure distance connue jusqu'ici — et l'on répète une seule opération : prendre le sommet provisoire de plus petite étiquette, la déclarer définitive, et mettre à jour ses voisins. Le raisonnement qui justifie ce culot est simple : puisque tous les coûts sont positifs, aucun détour ne pourra jamais faire mieux qu'un chemin déjà plus long au départ.

Le contrôle des sous-chemins n'est pas décoratif : la page reprend le chemin trouvé, en extrait chaque portion, et vérifie que sa longueur est bien la distance optimale entre ses deux extrémités. C'est le principe d'optimalité de Bellman, vérifié case par case — et c'est lui qui autorise à ne jamais revenir sur une étiquette déclarée définitive.

2Coûts négatifs : là où Dijkstra se trompe

Un coût peut être négatif : une étape qui rapporte, un tronçon subventionné, une conversion favorable. Dijkstra s'effondre alors, et pas discrètement — il rend une mauvaise réponse sans le signaler. La raison tient en une phrase : il fige une étiquette en pariant qu'aucun chemin plus long ne fera mieux ensuite, ce qui devient faux dès qu'un arc peut faire baisser le total.

Bellman-Ford renonce à ce pari : il relâche tous les arcs, n − 1 fois de suite. Après k passes, toutes les distances utilisant au plus k arcs sont exactes ; comme un plus court chemin sans circuit a au plus n − 1 arcs, on a fini. Et si une n-ième passe améliore encore quelque chose, c'est qu'il existe un circuit absorbant : le problème n'a plus de solution, on peut tourner en rond en gagnant à chaque tour.

Une application : l'arbitrage de devises

Si l'on remplace chaque taux de change par moins son logarithme, un circuit absorbant devient exactement une suite de conversions qui ramène plus que la mise de départ. Bellman-Ford est donc, tel quel, un détecteur d'arbitrage.

3A* : donner une direction à la recherche

Dijkstra explore dans toutes les directions à la fois : pour un trajet Paris-Rome, il visiterait Brest avant Milan. L'algorithme A* corrige ce gâchis en ajoutant à chaque étiquette une estimation h de ce qu'il reste à parcourir — ici la distance à vol d'oiseau — et en choisissant le sommet qui minimise d + h. Tant que l'estimation ne surestime jamais la distance réelle, le résultat reste exactement optimal, mais l'exploration se resserre en un fuseau autour de la ligne droite.

Le balayage montre le compromis en entier. À poids nul, A* est Dijkstra. À poids 1, l'estimation est admissible — la distance à vol d'oiseau ne peut pas dépasser la distance réelle — et l'on gagne beaucoup d'exploration sans rien perdre. Au-delà, on va plus vite encore mais l'on n'a plus aucune garantie : c'est le domaine des heuristiques gloutonnes, où l'on échange de l'exactitude contre du temps en connaissance de cause.

4Tous les couples à la fois : Floyd-Warshall

Quand il faut les distances entre tous les couples, relancer Dijkstra n fois marche, mais il existe plus élégant. Floyd et Warshall proposent une récurrence sur les sommets autorisés comme intermédiaires : notons D_k(i,j) la meilleure distance n'empruntant que les sommets 1…k comme relais. Alors

D_k(i,j) = min( D_k−1(i,j) , D_k−1(i,k) + D_k−1(k,j) )

— soit on ne passe pas par k, soit on y passe, et le chemin se coupe alors en deux morceaux qu'on connaît déjà. Trois boucles imbriquées, six lignes de code, et toute la matrice des distances.