Deterministic Negative-Weight Shortest Paths in Nearly Linear Time via Path Covers
Bernhard Haeupler, Yonggang Jiang, Thatchaphol Saranurak
我们提出了第一个确定性的近线性时间算法,用于在定向图形上具有负边缘权重的单源最短路径:给定一个带有n顶点的定向图G,其权重在{-W,...,W}中为整数的m边缘,我们的算法要么计算来自源s的所有距离,要么报告时间Õ(m)·log(nW)的负周期。 此问题的所有已知近线性时间算法都是固有的随机化,因为它们主要依赖于低直径分解。 为了克服这个障碍,我们引入了一种新的结构原语,用于定向图形,称为路径覆盖。 这在无向图中具有类似于邻域覆盖的作用,这些图形长期以来一直是去随机化算法的核心,这些算法在无方向设置中使用低直径分解。 我们相信,路径覆盖将成为在定向图形上设计未来确定性算法的基本工具。
We present the first deterministic nearly-linear time algorithm for single-source shortest paths with negative edge weights on directed graphs: given a directed graph G with n vertices, m edges whose weights are integer in {-W,…,W}, our algorithm either computes all distances from a source s or reports a negative cycle in time Õ(m)·log(nW) time. All known near-linear time algorithms for this problem have been inherently randomized, as they crucially rely on low-diameter decompositions. To overco...