本科必学Dijkstra算法被超越！清华段然团队打破图灵奖得主证明的普遍最优性

** 清华大学段然团队成功研发出一种超越经典Dijkstra算法的最短路径新算法，首次突破了持续四十多年的“排序障碍”。该算法通过引入节点聚类、图分层和Bellman-Ford策略，无需排序即可在有向图和无向图上实现更快搜索。Dijkstra算法曾在2024年被图灵奖得主Tarjan团队证明为普遍最优，但新算法打破了这一理论边界。研究成果发表于STOC 2025并获最佳论文奖，被认为接近计算效率的极限，未来或在导航、网络路由等领域带来实际应用提升。
来源：https://mp.weixin.qq.com/s/OmiSCbea5qBT6JYhWYqQ-g