论文标题
负重量单源最短路径在近线性时间内
Negative-Weight Single-Source Shortest Paths in Near-linear Time
论文作者
论文摘要
我们提出了一种随机算法，该算法在$ o（m \ log^8（n）\ log w）中计算单源最短路径（SSSP）$ w）$ w）$ w）$ w）$ time当边缘权重积分并且可能为负。从本质上讲，这解决了经典的负重SSSP问题。先前的界限是$ \ tilde o（（（m+n^{1.5}）\ log w）$ [blnpsssw focs'20]和$ m^{4/3+o（1）} \ log w $ [amv focs'20]。近线性时间算法先前仅以平面定向图的特殊情况[Fakcharoenphol和Rao focs'01]而闻名。 与所有依赖复杂的连续优化方法和动态算法的最新发展相反，我们的算法很简单：它仅需要一个简单的图形分解和基本组合工具。实际上，我们的是第一种负重SSSP的组合算法，可以突破经典的$ \ tilde o（m \ sqrt {n} \ log w）$ bound三十多年前[Gabow and Tarjan sicomp'89]。
We present a randomized algorithm that computes single-source shortest paths (SSSP) in $O(m\log^8(n)\log W)$ time when edge weights are integral and can be negative. This essentially resolves the classic negative-weight SSSP problem. The previous bounds are $\tilde O((m+n^{1.5})\log W)$ [BLNPSSSW FOCS'20] and $m^{4/3+o(1)}\log W$ [AMV FOCS'20]. Near-linear time algorithms were known previously only for the special case of planar directed graphs [Fakcharoenphol and Rao FOCS'01]. In contrast to all recent developments that rely on sophisticated continuous optimization methods and dynamic algorithms, our algorithm is simple: it requires only a simple graph decomposition and elementary combinatorial tools. In fact, ours is the first combinatorial algorithm for negative-weight SSSP to break through the classic $\tilde O(m\sqrt{n}\log W)$ bound from over three decades ago [Gabow and Tarjan SICOMP'89].
