  In this paper we consider the decremental single-source shortest paths (SSSP)
problem, where given a graph $G$ and a source node $s$ the goal is to maintain
shortest distances between $s$ and all other nodes in $G$ under a sequence of
online adversarial edge deletions. In their seminal work, Even and Shiloach
[JACM 1981] presented an exact solution to the problem in unweighted graphs
with only $O(mn)$ total update time over all edge deletions. Their classic
algorithm was the state of the art for the decremental SSSP problem for three
decades, even when approximate shortest paths are allowed.
  A series of results showed how to improve upon $O(mn)$ if approximation is
allowed, culminating in a recent breakthrough of Henzinger, Krinninger and
Nanongkai [FOCS 14], who presented a $(1+\epsilon)$-approximate algorithm for
undirected weighted graphs whose total update time is near linear:
$O(m^{1+o(1)}\log(W))$, where $W$ is the ratio of the heaviest to the lightest
edge weight in the graph. In this paper they posed as a major open problem the
question of derandomizing their result.
  Until very recently, all known improvements over the Even-Shiloach algorithm
were randomized and required the assumption of a non-adaptive adversary. In
STOC 2016, Bernstein and Chechik showed the first \emph{deterministic}
algorithm to go beyond $O(mn)$ total update time: the algorithm is also
$(1+\epsilon)$-approximate, and has total update time $\tilde{O}(n^2)$. In SODA
2017, the same authors presented an algorithm with total update time
$\tilde{O}(mn^{3/4})$. However, both algorithms are restricted to undirected,
unweighted graphs. We present the \emph{first} deterministic algorithm for
\emph{weighted} undirected graphs to go beyond the $O(mn)$ bound. The total
update time is $\tilde{O}(n^2 \log(W))$.
