🔻论文显示：清华大学为主的团队刚刚发现了 40 年来最快的图最短路径算法。
🔻该算法改进了图灵奖得主 Tarjan 与 Dijkstra 共同提出的 O(m + n log n)复杂度——这是每位计算机专业学生在大学都会学习的经典算法。
🔻新算法在非负整数权重的图上实现了 O(m + n log log n)时间复杂度的单源最短路径(SSSP)计算。创新的核心在于用新型或改进的数据结构替代了 Dijkstra 算法中传统的优先队列，这些新结构支持更快速的降权值和提取最小值操作，从而实现了近乎线性的时间复杂度。
🔻该算法缩小了特定图类型（如平面图或整数权重图）专用算法与通用图上单源最短路径问题之间的差距。它将最短路径计算的下限推向边计数复杂度（O(m)）附近，这对稀疏图而言理论上已达到最优。可能促使计算机科学界重新审视经典算法及其底层数据结构。
🔻这是计算机科学重大突破，这一变革可能引发技术领域算法升级的新浪潮——关注后续连锁反应。
🔻该论文获 ACM 计算理论研讨会 （STOC 2025） 最佳论文奖。 获邀发表于 ACM 期刊。
🔻论文作者：清华大学交叉信息研究院长聘副教授段然、清华大学交叉信息研究院博士生 Jiayi Mao、斯坦福大学计算机科学专业博士生 Xiao Mao、马克斯·普朗克信息学研究所的博士后研究员 Xinkai Shu、清华大学交叉信息研究院博士生 Longhui Yin。
#热点现场#