  In the decremental single-source shortest paths (SSSP) problem we want to
maintain the distances between a given source node $s$ and every other node in
an $n$-node $m$-edge graph $G$ undergoing edge deletions. While its static
counterpart can be solved in near-linear time, this decremental problem is much
more challenging even in the undirected unweighted case. In this case, the
classic $O(mn)$ total update time of Even and Shiloach [JACM 1981] has been the
fastest known algorithm for three decades. At the cost of a
$(1+\epsilon)$-approximation factor, the running time was recently improved to
$n^{2+o(1)}$ by Bernstein and Roditty [SODA 2011]. In this paper, we bring the
running time down to near-linear: We give a $(1+\epsilon)$-approximation
algorithm with $m^{1+o(1)}$ expected total update time, thus obtaining
near-linear time. Moreover, we obtain $m^{1+o(1)} \log W$ time for the weighted
case, where the edge weights are integers from $1$ to $W$. The only prior work
on weighted graphs in $o(m n)$ time is the $m n^{0.9 + o(1)}$-time algorithm by
Henzinger et al. [STOC 2014, ICALP 2015] which works for directed graphs with
quasi-polynomial edge weights. The expected running time bound of our algorithm
holds against an oblivious adversary.
  In contrast to the previous results which rely on maintaining a sparse
emulator, our algorithm relies on maintaining a so-called sparse $(h,
\epsilon)$-hop set introduced by Cohen [JACM 2000] in the PRAM literature. An
$(h, \epsilon)$-hop set of a graph $G=(V, E)$ is a set $F$ of weighted edges
such that the distance between any pair of nodes in $G$ can be
$(1+\epsilon)$-approximated by their $h$-hop distance (given by a path
containing at most $h$ edges) on $G'=(V, E\cup F)$. Our algorithm can maintain
an $(n^{o(1)}, \epsilon)$-hop set of near-linear size in near-linear time under
edge deletions.
