  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.
