  A \emph{metric tree embedding} of expected \emph{stretch~$\alpha \geq 1$}
maps a weighted $n$-node graph $G = (V, E, \omega)$ to a weighted tree $T =
(V_T, E_T, \omega_T)$ with $V \subseteq V_T$ such that, for all $v,w \in V$,
$\operatorname{dist}(v, w, G) \leq \operatorname{dist}(v, w, T)$ and
$operatorname{E}[\operatorname{dist}(v, w, T)] \leq \alpha
\operatorname{dist}(v, w, G)$. Such embeddings are highly useful for designing
fast approximation algorithms, as many hard problems are easy to solve on tree
instances. However, to date the best parallel $(\operatorname{polylog}
n)$-depth algorithm that achieves an asymptotically optimal expected stretch of
$\alpha \in \operatorname{O}(\log n)$ requires $\operatorname{\Omega}(n^2)$
work and a metric as input.
  In this paper, we show how to achieve the same guarantees using
$\operatorname{polylog} n$ depth and $\operatorname{\tilde{O}}(m^{1+\epsilon})$
work, where $m = |E|$ and $\epsilon > 0$ is an arbitrarily small constant.
Moreover, one may further reduce the work to $\operatorname{\tilde{O}}(m +
n^{1+\epsilon})$ at the expense of increasing the expected stretch to
$\operatorname{O}(\epsilon^{-1} \log n)$.
  Our main tool in deriving these parallel algorithms is an algebraic
characterization of a generalization of the classic Moore-Bellman-Ford
algorithm. We consider this framework, which subsumes a variety of previous
"Moore-Bellman-Ford-like" algorithms, to be of independent interest and discuss
it in depth. In our tree embedding algorithm, we leverage it for providing
efficient query access to an approximate metric that allows sampling the tree
using $\operatorname{polylog} n$ depth and $\operatorname{\tilde{O}}(m)$ work.
  We illustrate the generality and versatility of our techniques by various
examples and a number of additional results.
