  Given a directed, weighted graph $G=(V,E)$ undergoing edge insertions, the
incremental single-source shortest paths (SSSP) problem asks for the
maintenance of approximate distances from a dedicated source $s$ while
optimizing the total time required to process the insertion sequence of $m$
edges.
  Recently, Gutenberg, Williams and Wein [STOC'20] introduced a deterministic
$\tilde{O}(n^2)$ algorithm for this problem, achieving near linear time for
very dense graphs. For sparse graphs, Chechik and Zhang [SODA'21] recently
presented a deterministic $\tilde{O}(m^{5/3})$ algorithm, and an adaptive
randomized algorithm with run-time $\tilde{O}(m\sqrt{n} + m^{7/5})$. This
algorithm is remarkable for two reasons: 1) in very spare graphs it reaches the
directed hopset barrier of $\tilde{\Omega}(n^{3/2})$ that applied to all
previous approaches for partially-dynamic SSSP [STOC'14, SODA'20, FOCS'20]
\emph{and} 2) it does not resort to a directed hopset technique itself.
  In this article we introduce \emph{propagation synchronization}, a new
technique for controlling the error build-up on paths throughout batches of
insertions. This leads us to a significant improvement of the approach in
[SODA'21] yielding a \emph{deterministic} $\tilde{O}(m^{3/2})$ algorithm for
the problem. By a very careful combination of our new technique with the
sampling approach from [SODA'21], we further obtain an adaptive randomized
algorithm with total update time $\tilde{O}(m^{4/3})$. This is the first
partially-dynamic SSSP algorithm in sparse graphs to bypass the notorious
directed hopset barrier which is often seen as the fundamental challenge
towards achieving truly near-linear time algorithms.
