Deterministic Negative-Weight Shortest Paths in Nearly Linear Time via Path Covers
Abstract
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 O(m)· log(nW) time.
Fields of Study & Subjects
Complexity and Algorithms in Graphs
Advanced Graph Theory Research
Stochastic Gradient Optimization Techniques
Publication details
- Pages
- 198–209
- Publication date
- 9 June 2026
- Language
- EN