@techNmak: 38年来，计算机科学家们认为迪杰斯特拉算法在稀疏图中是最优的。这个逻辑似乎无懈可击…

X AI KOLs Timeline 论文
algorithm shortest-path dijkstra bellman-ford graph-theory theoretical-cs breakthrough

摘要

来自清华、斯坦福和马克斯·普朗克的五位研究人员开发了一种新的最短路径算法，在稀疏有向图中超越了迪杰斯特拉算法，实现了O(m log^(2/3) n)的时间复杂度，这是自1987年以来的首次改进。

38年来，计算机科学家们认为迪杰斯特拉算法在稀疏图中是最优的。 这个逻辑似乎无懈可击： 迪杰斯特拉算法按距离对顶点排序。 排序的下界是O(n log n)。 因此最短路径不可能更快。 5位研究人员证明了这个假设是错误的。 技巧：将迪杰斯特拉的优先队列与贝尔曼-福特的动态规划相结合。在顶点集上分而治之。缩小边界。 结果：O(m log^(2/3) n) 这是自1987年斐波那契堆以来对有向图首次改进。 清华。斯坦福。马克斯·普朗克。17页。
查看原文
查看缓存全文

缓存时间: 2026/06/09 12:47

38年来，计算机科学家一直认为迪杰斯特拉算法对于稀疏图是最优的。

这个逻辑看起来无懈可击：

迪杰斯特拉算法按距离对顶点排序。 排序的下界为 O(n log n)。 因此最短路径不可能更快。

5位研究人员证明了这一假设是错误的。

诀窍在于：将迪杰斯特拉的优先队列与贝尔曼-福德的动态规划相结合。对顶点集进行分治。缩小前沿边界。

结果：O(m log^(2/3) n) 自1987年斐波那契堆以来，有向图首次获得改进。

清华大学。斯坦福大学。马克斯·普朗克研究所。17页。

相似文章

@lxfater: 清华几个人把 Google Maps 用了 41 年的算法给超了 从 1984 年算到现在，41 年没人做到过 那个算法叫 Dijkstra，你没听过没关系，你每天都在用 但这个卡了 40 年突破不了，因为有一道数学上的排序屏障横在中间 …

X AI KOLs Timeline

Researchers from Tsinghua University have developed a new shortest-path algorithm with O(m log^{2/3} n) complexity, surpassing Dijkstra's algorithm which had been considered theoretically optimal for 41 years.

代数图上的搜索

Lobsters Hottest

本文讨论了直接在代数图表示上运行Dijkstra算法的方法，无需转换为邻接图，并利用了图压缩技术。

数学家构建期待已久的Graph Sandwich

Hacker News Top

数学家证明了图论中长期存在的sandwich conjecture，表明大型随机图可以近似于两个更简单图之间，连接不同的随机过程并推动该领域的发展。