  We present a $(1+\varepsilon)$-approximate parallel algorithm for computing
shortest paths in undirected graphs, achieving $\mathrm{poly}(\log n)$ depth
and $m\mathrm{poly}(\log n)$ work for $n$-nodes $m$-edges graphs. Although
sequential algorithms with (nearly) optimal running time have been known for
several decades, near-optimal parallel algorithms have turned out to be a much
tougher challenge. For $(1+\varepsilon)$-approximation, all prior algorithms
with $\mathrm{poly}(\log n)$ depth perform at least $\Omega(mn^{c})$ work for
some constant $c>0$. Improving this long-standing upper bound obtained by Cohen
(STOC'94) has been open for $25$ years.
  We develop several new tools of independent interest. One of them is a new
notion beyond hopsets --- low hop emulator --- a $\mathrm{poly}(\log
n)$-approximate emulator graph in which every shortest path has at most
$O(\log\log n)$ hops (edges). Direct applications of the low hop emulators are
parallel algorithms for $\mathrm{poly}(\log n)$-approximate single source
shortest path (SSSP), Bourgain's embedding, metric tree embedding, and low
diameter decomposition, all with $\mathrm{poly}(\log n)$ depth and
$m\mathrm{poly}(\log n)$ work.
  To boost the approximation ratio to $(1+\varepsilon)$, we introduce
compressible preconditioners and apply it inside Sherman's framework (SODA'17)
to solve the more general problem of uncapacitated minimum cost flow (a.k.a.,
transshipment problem). Our algorithm computes a $(1+\varepsilon)$-approximate
uncapacitated minimum cost flow in $\mathrm{poly}(\log n)$ depth using
$m\mathrm{poly}(\log n)$ work. As a consequence, it also improves the
state-of-the-art sequential running time from $m\cdot 2^{O(\sqrt{\log n})}$ to
$m\mathrm{poly}(\log n)$.
