  In the dynamic Single-Source Shortest Paths (SSSP) problem, we are given a
graph $G=(V,E)$ subject to edge insertions and deletions and a source vertex
$s\in V$, and the goal is to maintain the distance $d(s,t)$ for all $t\in V$.
  Fine-grained complexity has provided strong lower bounds for exact partially
dynamic SSSP and approximate fully dynamic SSSP [ESA'04, FOCS'14, STOC'15].
Thus much focus has been directed towards finding efficient partially dynamic
$(1+\epsilon)$-approximate SSSP algorithms [STOC'14, ICALP'15, SODA'14,
FOCS'14, STOC'16, SODA'17, ICALP'17, ICALP'19, STOC'19, SODA'20, SODA'20].
Despite this rich literature, for directed graphs there are no known
deterministic algorithms for $(1+\epsilon)$-approximate dynamic SSSP that
perform better than the classic ES-tree [JACM'81]. We present the first such
algorithm.
  We present a \emph{deterministic} data structure for incremental SSSP in
weighted digraphs with total update time $\tilde{O}(n^2 \log W)$ which is
near-optimal for very dense graphs; here $W$ is the ratio of the largest weight
in the graph to the smallest. Our algorithm also improves over the best known
partially dynamic \emph{randomized} algorithm for directed SSSP by Henzinger et
al. [STOC'14, ICALP'15] if $m=\omega(n^{1.1})$.
  We also provide improved conditional lower bounds. Henzinger et al. [STOC'15]
showed that under the OMv Hypothesis, the partially dynamic exact $s$-$t$
Shortest Path problem in undirected graphs requires amortized update or query
time $m^{1/2-o(1)}$, given polynomial preprocessing time. Under a hypothesis
about finding Cliques, we improve the update and query lower bound for
algorithms with polynomial preprocessing time to $m^{0.626-o(1)}$. Further,
under the $k$-Cycle hypothesis, we show that any partially dynamic SSSP
algorithm with $O(m^{2-\epsilon})$ preprocessing time requires amortized update
or query time $m^{1-o(1)}$.
