Faster Negative-Weight Shortest Paths and Directed Low-Diameter Decompositions

We present a faster algorithm for low-diameter decompositions on directed graphs, matching the \(O(\log n \log \log n)\) loss factor from Bringmann, Fischer, Haeupler, and Latypov (ICALP 2025) and improving the running time to \(O((m + n \log \log n) \log n \log \log n)\) in expectation. We then apply our faster low-diameter decomposition to obtain an algorithm for negative-weight single source shortest paths on integer-weighted graphs in \(O((m+n \log \log n) \log(nW) \log n \log \log n)\) time, a nearly log-factor improvement over the algorithm of Bringmann, Cassis, and Fischer (FOCS 2023).