Deterministic Negative-Weight Shortest Paths in Nearly Linear Time via Path Covers

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 integers in -W, . . . , W , our algorithm either computes all distances from a source s or reports a negative cycle in Õ(m)•log(nW ) time.

All known near-linear time algorithms for this problem have been inherently randomized [BNW25, BCF23, FHL + 25, LM24], as they crucially rely on low-diameter decompositions.

To overcome this barrier, we introduce a new structural primitive for directed graphs called the path cover. This plays a role analogous to neighborhood covers in undirected graphs [ABCP98], which have long been central to derandomizing algorithms that use low-diameter decomposition in the undirected setting. We believe that path covers will serve as a fundamental tool for the design of future deterministic algorithms on directed graphs.