Breaking the Bellman-Ford Shortest-Path Bound

Abstract

In this paper we give a single-source shortest-path algorithm that breaks, after over 60 years, the $O(n \cdot m)$ time bound for the Bellman-Ford algorithm, where $n$ is the number of vertices and $m$ is the number of arcs of the graph. Our algorithm converts the input graph to a graph with nonnegative weights by performing at most $\min(\sqrt{n},\sqrt{m/\log n})$ calls to Dijkstra's algorithm, such that the shortest-path tree is the same for the new graph as that for the original. When Dijkstra's algorithm is implemented using Fibonacci heaps, the running time of our algorithm is therefore $O(\sqrt{n} \cdot m + n \cdot \sqrt{m \log n})$. We also give a second implementation that performs few calls to Dijkstra's algorithm if the graph contains few negative arcs on the shortest-path tree.

Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.