In this work we revisit the fundamental Single-Source Shortest Paths (SSSP) problem with possibly negative edge weights. A recent breakthrough result by Bernstein, Nanongkai and Wulff-Nilsen established a near-linear $O(m \log^8(n) \log(W))$-time algorithm for negative-weight SSSP, where $W$ is an upper bound on the magnitude of the smallest negative-weight edge. In this work we improve the running time to $O(m \log^2(n) \log(nW) \log\log n)$, which is an improvement by nearly six log-factors. Some of these log-factors are easy to shave (e.g. replacing the priority queue used in Dijkstra's algorithm), while others are significantly more involved (e.g. to find negative cycles we design an algorithm reminiscent of noisy binary search and analyze it with drift analysis). As side results, we obtain an algorithm to compute the minimum cycle mean in the same running time as well as a new construction for computing Low-Diameter Decompositions in directed graphs.
翻译：在这项工作中，我们重新审视可能具有负边权重的基本单源最短路径问题。Bernstein、Nanongkai和Wulff-Nilsen最近取得的突破性成果，建立了一个近线性的$O(m \log^8(n) \log(W))$时间算法，用于解决负权最短路径问题，其中$W$是最小负权边权重的上界。在这项工作中，我们将运行时间提高到了$O(m \log^2(n) \log(nW) \log\log n)$，这是近六个对数因子的改进。其中一些对数因子很容易删减 (例如用Dijkstra算法中使用的优先队列进行替换)，而其他对数因子则需要显著更多的参与(例如，为了查找负循环，我们设计了一种回声二进制搜索算法，并用漂移分析来分析它)。作为副产物，我们在相同的运行时间内获得了计算最小循环均值的算法，以及一种针对有向图的新型低直径分解构造方法。
相关内容
微信扫码咨询专知VIP会员