  We study reachability and shortest paths problems in dynamic directed graphs.
Whereas algebraic dynamic data structures supporting edge updates and
reachability/distance queries have been known for quite a long time, they do
not, in general, allow reporting the underlying paths within the same time
bounds, especially against an adaptive adversary.
  In this paper we develop the first known fully dynamic reachability data
structures working against an adaptive adversary and supporting edge updates
and path queries for two natural variants: (1) point-to-point path reporting,
and (2) single-source reachability tree reporting. For point-to-point queries
in DAGs, we achieve $O(n^{1.529})$ worst-case update and query bounds, whereas
for tree reporting in DAGs, the worst-case bounds are $O(n^{1.765})$. More
importantly, we show how to lift these algorithms to work on general graphs at
the cost of increasing the bounds to $n^{1+5/6+o(1)}$ and making the update
times amortized. On the way to accomplishing that, we obtain two interesting
subresults. We give subquadratic fully dynamic algorithms for topological order
(in a DAG), and strongly connected components. To the best of our knowledge,
such algorithms have not been described before.
  Additionally, we provide deterministic incremental data structures for
reachability and shortest paths that handle edge insertions and report the
respective paths within subquadratic worst-case time bounds. For reachability
and $(1+\epsilon)$-approximate shortest paths in weighted digraphs, these
bounds match the best known dynamic matrix inverse-based randomized bounds for
fully dynamic reachability [v.d.Brand, Nanongkai and Saranurak, FOCS'19]. For
exact shortest paths in unweighted graphs, the obtained bounds in the
incremental setting polynomially improve upon the respective best known
randomized update/distance query bounds in the fully dynamic setting.
