推荐ckcheng · 2023-12
“It's apparently a very simple and approachable method.”
称这个近线性时间负权最短路径方法据说简单易懂
近线性时间求解含负权边的单源最短路径,方法简洁
给出一个随机算法,在整数且可为负的边权下,以 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) 界的组合算法。
评论者因为它据说方法非常简单、易上手而推荐,作为近线性负权最短路径的代表。
“It's apparently a very simple and approachable method.”