  In undirected graphs with real non-negative weights, we give a new randomized
algorithm for the single-source shortest path (SSSP) problem with running time
$O(m\sqrt{\log n \cdot \log\log n})$ in the comparison-addition model. This is
the first algorithm to break the $O(m+n\log n)$ time bound for real-weighted
sparse graphs by Dijkstra's algorithm with Fibonacci heaps. Previous undirected
non-negative SSSP algorithms give time bound of $O(m\alpha(m,n)+\min\{n\log n,
n\log\log r\})$ in comparison-addition model, where $\alpha$ is the
inverse-Ackermann function and $r$ is the ratio of the maximum-to-minimum edge
weight [Pettie & Ramachandran 2005], and linear time for integer edge weights
in RAM model [Thorup 1999]. Note that there is a proposed complexity lower
bound of $\Omega(m+\min\{n\log n, n\log\log r\})$ for hierarchy-based
algorithms for undirected real-weighted SSSP [Pettie & Ramachandran 2005], but
our algorithm does not obey the properties required for that lower bound. As a
non-hierarchy-based approach, our algorithm shows great advantage with much
simpler structure, and is much easier to implement.
