量子位
·
本科必学Dijkstra算法被超越！清华段然团队打破图灵奖得主证明的普遍最优性
💡
原文中文，约3000字，阅读约需7分钟。
📝
内容提要
清华大学段然团队突破Dijkstra算法速度限制，提出新算法解决“排序障碍”，实现更快的最短路径计算，标志着算法研究的重要里程碑。
🎯
关键要点
-
清华大学段然团队提出新算法，超越经典Dijkstra算法。
-
新算法解决了困扰研究人员四十多年的“排序障碍”。
-
该算法运行速度比任何Dijkstra及其改进算法都快。
-
新算法避免了整体排序，采用基于簇的方法提高效率。
-
研究团队从Bellman-Ford算法中汲取灵感，设计出新方法。
-
新算法在有向图和无向图上均快于Dijkstra算法。
-
该研究成果在STOC 2025会议上获得最佳论文奖。
-
段然教授及其团队计划进一步简化算法以提高速度。
❓
延伸问答
清华段然团队的新算法有什么突破？
新算法超越了Dijkstra算法，解决了困扰研究人员四十多年的“排序障碍”，实现了更快的最短路径计算。
新算法是如何提高效率的？
新算法采用基于簇的方法，避免了整体排序，从而提高了效率。
Dijkstra算法的普遍最优性是由谁证明的？
Dijkstra算法的普遍最优性是由图灵奖得主Robert Tarjan及其团队证明的。
新算法在什么类型的图上表现更好？
新算法在有向图和无向图上均快于Dijkstra算法。
段然教授的团队计划如何进一步改进算法？
团队计划进一步简化算法，以提高运行速度。
新算法的研究成果在哪个会议上获得了最佳论文奖？
该研究成果在STOC 2025会议上获得最佳论文奖。
➡️
