Improved Bounds for Directed SSSP in Sparse and Intermediate-Density Graphs
Abstract
We give a deterministic algorithm for exact single-source shortest paths (SSSP) in directed graphs with $n$ vertices, $m$ edges and nonnegative real edge weights. In the comparison-addition model, with unit-cost elementary operations on $O(\log(n+m+2))$-bit integer words, its running time for $m=O(n)$ is $O(n\sqrt{\log n}(\log\log n)^{1/4})$. For $m=Θ(n)$, this reduces the exponent of $\log\log n$ in the bound of Duan, Mao, Shu and Yin from $1/2$ to $1/4$ and removes the factor $(\log\log\log n)^{1/4}$ from the sparse bound stated in a public draft. The same algorithm improves on the bound of Duan et al. over a range of intermediate densities. At $m=Θ(n\sqrt{\log\log n})$, the running time is $O(n\sqrt{\log n}(\log\log n)^{5/8})$, reducing their exponent from $3/4$ to $5/8$. This is a consequence of a uniform bound for intermediate densities up to any fixed multiple of $n\log\log n$ edges; its validity range is larger than the range of strict improvement.
- Comment
- 69 pages