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.
Aucun commentaire pour le moment.