Quel est le trajet le plus court en métro?

Lorsqu'on cherche le chemin le plus court entre deux stations de métro, une approche naïve testant toutes les combinaisons possibles devient rapidement impraticable : avec 30 stations, un supercalculateur mettrait plus de 2 982 siècles. Heureusement, un algorithme bien plus efficace existe : explorer les stations voisines par « couches » de distance croissante. Cette méthode résout le problème en moins d'une milliseconde même pour un réseau d'un million de stations.

Cependant, la situation change radicalement lorsqu'on souhaite visiter plusieurs lieux à différentes stations : il faut alors trouver l'itinéraire le plus court passant par tous ces points. Ce problème, connu sous le nom de problème du voyageur de commerce, n'admet pas d'algorithme efficace garanti. Cette différence entre problèmes « faciles » (classe P) et « difficiles » (classe NP) soulève l'une des grandes questions de l'informatique et des mathématiques : P est-il égal à NP ? Les chercheurs en doutent et travaillent à développer des approches heuristiques pour obtenir de bonnes solutions aux problèmes difficiles.