Des chercheurs de l’université Tsinghua, en collaboration avec l’université Stanford, ont réalisé une avancée majeure du point de vue de la complexité de calcul pour le problème classique du plus court chemin à source unique (single-source shortest path, SSSP). Cette recherche a remporté le prix du meilleur article à la conférence STOC 2025.
La méthode traditionnellement la plus utilisée est l’algorithme de Dijkstra, dont la complexité temporelle est de la forme O(m + n log n) (n = nombre de nœuds, m = nombre d’arêtes).
Le terme log n est lié à la file de priorité (priority queue) ou au tri (sorting), et aucune amélioration n’avait permis de dépasser cette partie au cours des 40 dernières années.
Le nouvel algorithme réduit la complexité temporelle à O(m · log^(2/3) n).
Comme log^(2/3) n croît plus lentement que log n (autrement dit, augmente moins que log n), l’écart devient important lorsque le nombre de nœuds est très grand.
18 commentaires
Ça me rappelle mes souvenirs (?) de la fin des années 2000, quand je travaillais dans une entreprise de logiciels de navigation automobile et que je développais un module de recherche d’itinéraire.
On n’utilise pas Dijkstra pour la recherche d’itinéraire en navigation, car c’est trop lent ; on emploie plutôt A* (A Star), une version améliorée par heuristique. En vérifiant, je vois qu’A* n’est pas un algorithme SSSP mais SPSP (Single-Pair Shortest Path).
Dans le cas où le graphe est sparse, il me semble discutable d’affirmer qu’il surpasse l’algorithme rapide existant.
Cela ne fait pas si longtemps que CLRS a été révisé, ils vont déjà en imprimer une nouvelle édition ?
C’est un peu comme si les Beatles ou Oasis, des groupes apparus il y a longtemps et toujours populaires aujourd’hui, sortaient un nouvel album après 41 ans. D’abord, ça surprend et ça suscite l’intérêt, haha.
Les États-Unis l’avaient peut-être déjà ? 😨😨😨
C’est magnifique, pfiouuuu
La Chine est en train de prendre de l’avance ces derniers temps.
Je me demande comment le nom de l’algorithme va être choisi.
Quelqu’un va sans doute bientôt proposer un problème sur Baekjoon avec ces contraintes, j’en frémis déjà d’impatience.
La nostalgie de Dijkstra..
Waouh... c'est énorme...
C'est impressionnant.
Waouh......
C’est donc possible...
Wouah~~
Wah....
On dirait qu’il va falloir ajouter ça au contenu des cours d’algorithmique lol
Aïe...