Manoj Gupta lève un verrou vieux de 1996 sur les plus courts chemins

Manoj Gupta, de l'Indian Institute of Technology Gandhinagar, a mis au point un algorithme qui dépasse une limite connue de l'informatique depuis 1996. Sa méthode fournit des approximations plus précises des plus courts chemins entre des points proches, sans augmenter le temps de calcul.

Le calcul de plus courts chemins est une tâche quotidienne pour les ordinateurs : applications de navigation, systèmes de transport et infrastructure d'internet en dépendent. Elle devient bien plus ardue lorsqu'il faut déterminer les distances entre toutes les paires de points d'un très grand réseau, problème connu sous le nom d'APSP (All-Pairs Shortest Paths). Un réseau est ici un ensemble de points reliés entre eux, représentant des villes, des ordinateurs, des gares, voire des neurones.

La faiblesse de la méthode de 1996

Calculer exactement tous les trajets dans un réseau vaste et dense exige des ressources considérables. Les chercheurs cherchent donc depuis longtemps des méthodes fiables qui évitent d'examiner chaque chemin. En 1996, Dor, Halperin et Zwick ont proposé un algorithme garantissant une estimation au plus égale au double du plus court chemin réel, une approximation de facteur 2.

Mais cette garantie valait surtout pour des points éloignés. Sur de courtes liaisons, l'erreur pouvait être plus grande : un trajet réel de deux liens pouvait être estimé à cinq, dépassant la marge du double.

L'apport de Gupta

Gupta améliore la manière de choisir les points servant à l'estimation. L'approche antérieure s'appuyait sur un ensemble assez restreint de sommets représentatifs. Le nouvel algorithme recourt à un échantillonnage multi-échelle : il analyse la structure du réseau à plusieurs niveaux plutôt que de dépendre d'un seul jeu de points.

La méthode prend ainsi en compte des liaisons plus courtes, auparavant négligées. Surtout, ce gain de précision n'alourdit pas la complexité globale de l'algorithme : les résultats sont plus fiables sans temps d'exécution supplémentaire.

Cette avancée pourrait intéresser les télécommunications, les transports, les réseaux sociaux et les systèmes d'intelligence artificielle, où une estimation rapide et fiable des distances facilite l'analyse des dépendances et l'optimisation de systèmes entiers.