10 agents Opus 5.5 découvrent un algorithme de plus court chemin surpassant Dijkstra en 15 heures

Le problème du plus court chemin est un défi classique de la théorie des graphes, fondamental pour la navigation moderne, le routage Internet, la logistique et d'innombrables autres applications réelles. En 1959, le scientifique informatique néerlandais Edsger Dijkstra a proposé un algorithme d'une complexité de O(m + n log n), qui est resté l'étalon-or pendant 65 ans et a été utilisé de manière omniprésente.

En 2025, une équipe de l'Université Tsinghua, de Stanford et de l'Institut Max Planck a finalement dépassé cette limite avec une borne de O(m log^{2/3} n). Cependant, l'avantage de leur solution ne se manifeste que sur des graphes suffisamment denses (où le nombre d'arêtes m ≥ le nombre de sommets n). Sur les graphes épars, l'algorithme de Dijkstra est resté supérieur.

Vals AI a décidé de tester le nouveau modèle Opus 5.5 spécifiquement sur ce domaine inexploré (article de blog). Ils ont lancé 10 agents, leur ont assigné la tâche et leur ont fourni un « tableau d'affichage » pour échanger des idées et coopérer.

En conséquence, en 15 heures et 733 messages, les agents ont dérivé l'algorithme C-HD et l'ont vérifié formellement. Il s'agit de la première amélioration prouvée spécifiquement dans la zone épaisse où Dijkstra était encore le meilleur : à m ≈ n·log^{3/4}n, C-HD atteint O(n·log^{11/12}n) contre O(n log n) pour Dijkstra. À n = 2^1000, le gain est d'environ 1,78x et augmente avec la taille du graphe.

Cependant, malgré l'affirmation impressionnante et l'existence d'une preuve en Lean, il n'est pas encore question d'accélération pratique, car les estimations ci-dessus sont asymptotiques. L'algorithme n'a pas encore été testé sur des graphes réels. En d'autres termes, bien qu'une courbe soit garantie de dépasser l'autre lorsque n → ∞, le point de croisement en pratique ne peut se produire qu'à des valeurs énormes de n, et sur tout graphe réaliste, Dijkstra sera probablement toujours plus rapide malgré une asymptotique moins bonne. Cette partie reste à vérifier.