  We present a general toolbox, based on new vertex sparsifiers, for designing
data structures to maintain shortest paths in dynamic graphs.
  In an $m$-edge graph undergoing edge insertions and deletions, our data
structures give the first algorithms for maintaining (a) $m^{o(1)}$-approximate
all-pairs shortest paths (APSP) with \emph{worst-case} update time $m^{o(1)}$
and query time $\tilde{O}(1)$, and (b) a tree $T$ that has diameter no larger
than a subpolynomial factor times the diameter of the underlying graph, where
each update is handled in amortized subpolynomial time.
  In graphs undergoing only edge deletions, we develop a simpler and more
efficient data structure to maintain a $(1+\epsilon)$-approximate single-source
shortest paths (SSSP) tree $T$ in a graph undergoing edge deletions in
amortized time $m^{o(1)}$ per update.
  Our data structures are deterministic. The trees we can maintain are not
subgraphs of $G$, but embed with small edge congestion into $G$. This is in
stark contrast to previous approaches and is useful for algorithms that
internally use trees to route flow.
  To illustrate the power of our new toolbox, we show that our SSSP data
structure gives simple deterministic implementations of flow-routing MWU
methods in several contexts, where previously only randomized methods had been
known.
  To obtain our toolbox, we give the first algorithm that, given a graph $G$
undergoing edge insertions and deletions and a dynamic terminal set $A$,
maintains a vertex sparsifier $H$ that approximately preserves distances
between terminals in $A$, consists of at most $|A|m^{o(1)}$ vertices and edges,
and can be updated in worst-case time $m^{o(1)}$.
  Crucially, our vertex sparsifier construction allows us to maintain a low
edge-congestion embedding of $H$ into $G$, which is needed for our
applications.
