  We introduce stronger notions for approximate single-source shortest-path
distances, show how to efficiently compute them from weaker standard notions,
and demonstrate the algorithmic power of these new notions and transformations.
One application is the first work-efficient parallel algorithm for computing
exact single-source shortest paths graphs -- resolving a major open problem in
parallel computing.
  Given a source vertex in a directed graph with polynomially-bounded
nonnegative integer lengths, the algorithm computes an exact shortest path tree
in $m \log^{O(1)} n$ work and $n^{1/2+o(1)}$ depth. Previously, no parallel
algorithm improving the trivial linear depths of Dijkstra's algorithm without
significantly increasing the work was known, even for the case of undirected
and unweighted graphs (i.e., for computing a BFS-tree).
  Our main result is a black-box transformation that uses $\log^{O(1)} n$
standard approximate distance computations to produce approximate distances
which also satisfy the subtractive triangle inequality (up to a
$(1+\varepsilon)$ factor) and even induce an exact shortest path tree in a
graph with only slightly perturbed edge lengths. These strengthened
approximations are algorithmically significantly more powerful and overcome
well-known and often encountered barriers for using approximate distances. In
directed graphs they can even be boosted to exact distances. This results in a
black-box transformation of any (parallel or distributed) algorithm for
approximate shortest paths in directed graphs into an algorithm computing exact
distances at essentially no cost. Applying this to the recent breakthroughs of
Fineman et al. for compute approximate SSSP-distances via approximate hopsets
gives new parallel and distributed algorithm for exact shortest paths.
