“We give a deterministic O(mlog2/3n)-time algorithm for single-source shortest paths (SSSP) on directed graphs with real non-negative edge weights in the comparison-addition model.”
按年被提到
20252025 · 13 次2026
Breaking the Sorting Barrier for Directed Single-Source Shortest Paths
突破有向图单源最短路径的排序壁垒
Ran Duan, Jiayi Mao, Xiao Mao, Xinkai Shu, Longhui Yin · 2025
首个在稀疏图上突破 Dijkstra 时间界的确定性 SSSP 算法
被提及 · 16 人首次 2025-05-18 · 最近 2026-02-23发表于 ACM Symposium on Theory of Computing (STOC)
16不同的人
5活跃月份
15讨论串
21被引(OpenAlex)
论文给出一个确定性算法,在比较-加法模型下求解非负实数边权有向图的单源最短路径(SSSP),时间复杂度为 O(m log^{2/3} n)。这是第一个在稀疏图上突破 Dijkstra 算法 O(m + n log n) 时间界的结果,说明 Dijkstra 算法对 SSSP 并非最优。
HN 为什么提它
评论者围绕这篇 STOC 2025 最佳论文讨论:它在稀疏有向图上打破了 Dijkstra 的时间界,但可能只在很大的稀疏图上才更快,也有人动手实现了它。
方法难度 5 / 5约 120 分钟经得起时间
读之前最好知道
1Dijkstra 算法与优先队列(堆)
2算法时间复杂度分析
3比较-加法模型(comparison-addition model)
4图算法与最短路径
HN 书评
推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及引用supernetworks_ · 2025-08
引用摘要:比较加法模型下有向图单源最短路径的确定性 O(mlog2/3n) 算法
引用CMay · 2025-10
“The paper also indicates it works on directed graphs: Breaking the Sorting Barrier for Directed Single-Source Shortest Paths”
指出论文说明它适用于有向图,可能只在大型稀疏图上更快
引用Jtsummers · 2026-02
“Breaking the Sorting Barrier for Directed Single-Source Shortest Paths - Linked from the second sentence of the submission, not hard to track down.”
指出论文 PDF 链接就在提交内容第二句,不难找到
引用fn-mote · 2026-02
“Should have a more conspicuous link to the Quanta article that it references if not the original.”
指出该页面应更醒目地链接到所引用的 Quanta 文章或原论文
引用danalec · 2026-02
“I implemented the STOC 2025 Best Paper Award winner in C99.”
说自己用 C99 实现了这篇 STOC 2025 最佳论文奖的算法
被提交为 story · 11 次
- Breaking the Sorting Barrier for Directed Single-Source Shortest Paths ↗thomasahle · 2025-05-18 · 2 分
- Breaking the Sorting Barrier for Directed Single-Source Shortest Paths ↗pizza · 2025-05-19 · 2 分
- Breaking the Sorting Barrier for Directed Single-Source Shortest Paths ↗jonbaer · 2025-05-28 · 3 分
- Breaking the Sorting Barrier for Directed Single-Source Shortest Paths ↗mahmoudimus · 2025-05-29 · 17 分
- Breaking the Sorting Barrier for Directed Single-Source Shortest Paths ↗marvinborner · 2025-05-30 · 2 分
- Breaking the Sorting Barrier for Directed Single-Source Shortest Paths [pdf] ↗karussell · 2025-06-01 · 2 分