Negative-Weight Single-Source Shortest Paths in Near-Linear Time: Now Faster!
Open Access
- 6 November 2023
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 515-538
Abstract
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\left(m \log ^{8}(n) \log (W)\right)$-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\left(m \log ^{2}(n) \log (n W) \log \log n\right)$, 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.
Keywords
All Related Versions
Funding Information
- European Research Council
- Horizon Europe
This publication has 54 references indexed in Scilit:
- Negative-cycle detection algorithmsMathematical Programming, 1999
- Surpassing the information theoretic bound with fusion treesJournal of Computer and System Sciences, 1993
- Low diameter graph decompositionsCombinatorica, 1993
- Bounded ordered dictionaries in O(log log N) time and O(n) spaceInformation Processing Letters, 1990
- Faster algorithms for the shortest path problemJournal of the ACM, 1990
- Complexity of network synchronizationJournal of the ACM, 1985
- A characterization of the minimum cycle mean in a digraphDiscrete Mathematics, 1978
- Design and implementation of an efficient priority queueTheory of Computing Systems, 1976
- Algorithm 230: Matrix PermutationCommunications of the ACM, 1964
- A note on two problems in connexion with graphsNumerische Mathematik, 1959