按年被提到
20222022 · 2 次2026
算法与数据结构›经典算法与数据结构·arXiv:2203.03456 · cs.DS

Negative-Weight Single-Source Shortest Paths in Near-linear Time

近线性时间的负权单源最短路径
Aaron Bernstein, Danupon Nanongkai, Christian Wulff-Nilsen · 2022

近线性时间求解含负权边的单源最短路径,方法简洁

开始阅读 ↗PDFalphaXiv 讨论
被推荐 · 4 人首次 2022-11-14 · 最近 2023-12-22发表于 Annual Symposium on Foundations of Computer Science
4不同的人
3活跃月份
4讨论串
25被引(OpenAlex)

给出一个随机算法,在整数且可为负的边权下,以 O(m log^8(n) log W) 时间计算单源最短路径,基本解决了经典的负权 SSSP 问题,此前最好的界为 Õ((m+n^1.5) log W) 和 m^(4/3+o(1)) log W。与近年依赖复杂连续优化和动态算法的做法不同,该算法只需简单的图分解和初等组合工具,是第一个突破三十多年前 Õ(m√n log W) 界的组合算法。

HN 为什么提它

评论者因为它据说方法非常简单、易上手而推荐,作为近线性负权最短路径的代表。

方法难度 5 / 5约 90 分钟经得起时间
读之前最好知道
1Bellman-Ford 与 Dijkstra 算法
2图分解(graph decomposition)
3势函数与边权重标定(reweighting)
4随机算法分析

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
推荐ckcheng · 2023-12

“It's apparently a very simple and approachable method.”

称这个近线性时间负权最短路径方法据说简单易懂
The Biggest Discoveries in Computer Science in 2023原评论 ↗
被提交为 story · 3 次