Breaking the Bellman-Ford Shortest-Path Bound

Amr Elmasry

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 numbe…