38 年来首次突破,五位研究者改写稀疏有向最短路径经典复杂度界
techNmak · x · 2026-09-03
经典结论被打破:1985 年以来,稀疏有向图最短路径问题没有任何算法能击败 Dijkstra 的 O(m + n log n) 复杂度上界。2025 年,Duan、Mao、Mao、Shu、Yin 五位研究者终于给出了更快的算法。
突破的关键在哪
- Dijkstra 每次都选当前已知距离最小的未完成顶点,因此顶点严格按距离递增顺序被处理。
- 在「比较-加法」模型下,如果要求按距离顺序输出顶点,Dijkstra 已是最优——这不是实现问题,而是顺序本身就是额外约束。
- 但最短路径问题只要求最终距离值,并不要求有序输出。新算法正是利用了这一缝隙。
新算法的做法
作者没有执着于每次找出单个最近顶点,而是混合了三种技术:Dijkstra 式的探索、Bellman-Ford 式的松弛,以及分治(divide-and-conquer),按块处理顶点而非逐个按序处理,从而绕开了顺序约束带来的下界,在稀疏有向图上超越了保持 38 年的 O(m + n log n) 界。
这是理论计算机科学的标志性进展,对图的距离/顺序问题系列研究有直接影响。
「研究」频道最新
- Jan Kulveit 论复杂系统:两物交互难测,百万部件反可预测 — gleech · 2026-09-03
- 改 llama.cpp 内存表,实现 Qwen 知识热插拔注入 — ortegaalfredo · 2026-09-03
- Qwen 发布 E-Commerce Bench:智能体开店 365 天几乎没有模型学会赚钱 — Alibaba_Qwen · 2026-09-03
- 分析称 OpenAI 若在 Astra 上用 Looped Transformer,必已验证可扩展 — teortaxesTex · 2026-09-03
- 仅凭 EEG 信号实现「读梦」,神经对比学习解码人类睡眠活动 — Dr_Alex_Crimi · 2026-09-03
- 862 位历史数学难题被破解,但 2048 位密钥仍是天文数字 — bookwormengr · 2026-09-03