  This paper presents a randomized algorithm for the problem of single-source
shortest paths on directed graphs with real (both positive and negative) edge
weights. Given an input graph with $n$ vertices and $m$ edges, the algorithm
completes in $\tilde{O}(mn^{8/9})$ time with high probability. For
real-weighted graphs, this result constitutes the first asymptotic improvement
over the classic $O(mn)$-time algorithm variously attributed to Shimbel,
Bellman, Ford, and Moore.
