Briser la barrière du tri : un nouvel algorithme accélère la recherche du plus court chemin
2025-08-07
Pendant des décennies, un problème classique en informatique — trouver le plus court chemin depuis un point de départ spécifique dans un réseau jusqu'à tous les autres points — a été limité par une « barrière de tri ». Récemment, Ran Duan et son équipe de l’université Tsinghua ont brisé cette barrière en concevant un nouvel algorithme qui surpasse tous les algorithmes basés sur le tri en termes de vitesse. L’algorithme utilise intelligemment des stratégies de clustering et l’algorithme de Bellman-Ford, évitant le tri point par point et obtenant des améliorations de performance significatives, ouvrant ainsi un nouveau chapitre dans la recherche sur les problèmes de plus courts chemins.