Le problème des plus courts chemins

C'est l’histoire du livreur de pizzas, contraint de livrer ses commandes en moins d’une demi-heure avec pour seule arme un scooter faiblard et poussif. C'est aussi l’histoire de monsieur Dupont qui, sa valise à la main, se rend à la gare de Strasbourg, direction Biarritz, sans bien savoir par où passer. C'est encore l’histoire du goret centralien, synchronisant ses courses à l’Intermarché avec les horaires d’ouverture du cimetière d’Antony afin d’épargner à ses muscles endoloris par le Bang de la veille un bon kilomètre de marche avec les paquets sous les bras… C'est enfin l’histoire d’Internet qui permet le transfert de tous types de données dans le monde entier via… quelle route au fait ?

Dans les quatre cas, la question que se posent les protagonistes avant de foncer tête baissée est la même : quel est le plus court chemin pour aller de mon point de départ à mon point d’arrivée sachant que je ne peux emprunter que des lignes ferroviaires, des autoroutes, des cimetières ?

Qui dit trajet dit problème des plus courts chemins. Qui dit problème dit nécessité de trouver une solution. Dans les exemples précédents, la détermination d’un tel chemin est relativement simple, encore que pour monsieur Dupont, la seule solution consiste à se rendre au guichet ou à la borne automatique la plus proche et à attendre que l’ordinateur lui fournisse le résultat de ses recherches… exemple qui suffit à justifier la recherche d’algorithmes optimaux pour déterminer le chemin le plus court quand on connaît l’étendue du réseau SNCF, sans même parler du réseau Internet !

Le problème est donc posé : étant donné un ensemble de points (les gares, les serveurs) et un ensemble de liaisons entre ces points (les lignes ferroviaires, les routes, les cimetières) caractérisées par un certain poids (longueur en kilomètres ou, pourquoi pas, coût, nombre de tournants, débit,…), comment trouver le chemin le plus court, le moins cher, le plus agréable entre deux points ?

L’étude suivante présente l’algorithme de Dijkstra permettant de résoudre la question en O(a ln(n)) où n est le nombre de points et a le nombre de liaisons, ainsi qu'une implémentation en C++ dudit algorithme. Mais, pour bien le comprendre et réaliser à quel point il est rapide, il faut d’abord se familiariser avec les structures qui vont être utilisées pour représenter les données et exposer une solution « naïve » au problème, ce qui est justement le but des deux premières parties…