按年被提到
20252025 · 13 次2026
算法与数据结构›经典算法与数据结构·arXiv:2504.17033 · cs.DS

Breaking the Sorting Barrier for Directed Single-Source Shortest Paths

突破有向图单源最短路径的排序壁垒
Ran Duan, Jiayi Mao, Xiao Mao, Xinkai Shu, Longhui Yin · 2025

首个在稀疏图上突破 Dijkstra 时间界的确定性 SSSP 算法

开始阅读 ↗PDFalphaXiv 讨论
被提及 · 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

“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.”

引用摘要:比较加法模型下有向图单源最短路径的确定性 O(mlog2/3n) 算法
Breaking the sorting barrier for directed single-source shortest paths原评论 ↗
引用CMay · 2025-10

“The paper also indicates it works on directed graphs: Breaking the Sorting Barrier for Directed Single-Source Shortest Paths”

指出论文说明它适用于有向图,可能只在大型稀疏图上更快
A New Algorithm Makes It Faster to Find the 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 链接就在提交内容第二句,不难找到
Faster Than Dijkstra?原评论 ↗
引用fn-mote · 2026-02

“Should have a more conspicuous link to the Quanta article that it references if not the original.”

指出该页面应更醒目地链接到所引用的 Quanta 文章或原论文
Faster Than Dijkstra?原评论 ↗
引用danalec · 2026-02

“I implemented the STOC 2025 Best Paper Award winner in C99.”

说自己用 C99 实现了这篇 STOC 2025 最佳论文奖的算法
C99 implementation of new O(m log^(2/3) n) shortest path algorithm原评论 ↗
被提交为 story · 11 次