Recherche opérationnelle
Déterminer le trajet de coût, de distance ou de durée minimale entre deux points d'un réseau : l'énoncé est simple, la pratique l'est moins. Un réseau routier compte des millions de carrefours, les horaires changent la donne d'une minute à l'autre, et un calculateur d'itinéraire doit répondre en quelques millisecondes. Cette page part du problème posé — le plus court selon quoi ? — et va jusqu'aux techniques qui font vraiment tourner un GPS. Chaque affirmation est recalculée dans la page et confrontée à une méthode indépendante.
Sur la même carte, trois questions donnent trois routes différentes : la plus courte en kilomètres, la plus rapide, la moins chère. Un compromis linéaire « une minute vaut λ euros » en désigne une ; mais tous les itinéraires raisonnables ne s'obtiennent pas ainsi.
Sur un réseau de trains et de cars, une arête n'a pas de durée : elle a des horaires. Partir plus tôt ne garantit pas d'arriver plus tôt, attendre peut faire gagner une heure, et la correspondance de trois minutes qu'on rate coûte le prochain car. On balaie les connexions par heure de départ croissante — c'est l'algorithme utilisé par les calculateurs d'horaires.
Dijkstra explore en tache d'huile dans toutes les directions : sur un réseau réel, cela revient à visiter un pays entier pour aller d'une ville à sa voisine. Trois idées réduisent la tache sans jamais changer la réponse — chercher des deux bouts à la fois, orienter la recherche par la distance à vol d'oiseau, et remplacer celle-ci par une minoration bien meilleure obtenue à partir de quelques repères.
Un GPS ne recommence pas tout à chaque requête : il retravaille la carte une fois pour toutes. On classe les carrefours du moins important au plus important, on les retire un par un, et chaque fois qu'un retrait risque d'allonger un trajet on pose un raccourci qui mémorise le détour supprimé. La requête ne fait plus alors que monter dans la hiérarchie, des deux côtés à la fois.
Prenons le problème par l'autre bout : au lieu d'un trajet, calculons tous les trajets depuis un point, et regardons la forme de ce qui est accessible en t minutes. La boule du réseau n'est pas un disque : elle s'étire le long des autoroutes, et la distance à vol d'oiseau, elle, ment toujours dans le même sens.