  Algebraic data structures are the main subroutine for maintaining distances
in fully dynamic graphs in subquadratic time. However, these dynamic algebraic
algorithms generally cannot maintain the shortest paths, especially against
adaptive adversaries. We present the first fully dynamic algorithm that
maintains the shortest paths against an adaptive adversary in subquadratic
update time. This is obtained via a combinatorial reduction that allows
reconstructing the shortest paths with only a few distance estimates. Using
this reduction, we obtain the following:
  On weighted directed graphs with real edge weights in $[1,W]$, we can
maintain $(1+\epsilon)$ approximate shortest paths in
$\tilde{O}(n^{1.816}\epsilon^{-2} \log W)$ update and $\tilde{O}(n^{1.741}
\epsilon^{-2} \log W)$ query time. This improves upon the approximate distance
data structures from [v.d.Brand, Nanongkai, FOCS'19], which only returned a
distance estimate, by matching their complexity and returning an approximate
shortest path.
  On unweighted directed graphs, we can maintain exact shortest paths in
$\tilde{O}(n^{1.823})$ update and $\tilde{O}(n^{1.747})$ query time. This
improves upon [Bergamaschi, Henzinger, P.Gutenberg, V.Williams, Wein, SODA'21]
who could report the path only against oblivious adversaries. We improve both
their update and query time while also handling adaptive adversaries.
  On unweighted undirected graphs, our reduction holds not just against
adaptive adversaries but is also deterministic. We maintain a
$(1+\epsilon)$-approximate $st$-shortest path in $O(n^{1.529} / \epsilon^2)$
time per update, and $(1+\epsilon)$-approximate single source shortest paths in
$O(n^{1.764} / \epsilon^2)$ time per update. Previous deterministic results by
[v.d.Brand, Nazari, Forster, FOCS'22] could only maintain distance estimates
but no paths.
