  Exact computation of shortest paths in weighted graphs has been traditionally
studied in one of two settings. First, one can assume that the edge weights are
real numbers and all the performed operations on reals (typically comparisons
and additions) take constant time. Classical Dijkstra's and Bellman-Ford
algorithms have been described in this setting. More efficient exact shortest
paths algorithms have been obtained for integer-weighted graphs. Integrality
assumption not only enables faster algorithms but also allows implementing the
aforementioned algorithms in a much more realistic word RAM model where only
arithmetic operations on $O(\log{n})$-bit integers are performed in constant
time. On the word RAM one can as efficiently exactly encode even
\emph{rational-weighted} instances with $O(\log{n})$-bit numerators and
denominators. However, the known exact real-weighted shortest paths algorithms,
run on such a rational input, can easily encounter intermediate values of
$\Theta(n)$ bits if represented exactly. This leads to a factor-$\Omega(n)$
slowdown on the word RAM. At the same time, the scaling algorithms suited for
integer weights do not produce exact solutions for rational inputs without
dramatically increasing their accuracy.
  In this paper, we design randomized exact single-source shortest paths
algorithms for rational-weighted graphs on the word RAM. Most importantly, in
the non-negative case, we obtain a near-linear time algorithm matching
Dijkstra's algorithm running time up to polylogarithmic factors. In presence of
negative weights, we give an $\tilde{O}(n^{2.5})$-time algorithm breaking
through the best known strongly polynomial bound attained by Bellman-Ford for
sufficiently dense graphs.
