One advantage of the new notion of a "hop set" is that it yields a metric. For starters, note that we deal with two notions of distance: The "weighted distance" given by the sum of edge weights, and the "unweighted distance" given by their number (or "number of hops"). A "hop set" is a set of additional *weighted edges* and the original notion asks for the *existence* of a path *in the augmented graph* with (relatively) small weight (wrt original w-distance in the graph) that uses a small number of edges (or hops) between each pair of vertices. Since the bound on number of hops is a fixed parameter, the original notion does not satisfy triangle inequality. In contrast, the new notion talks about sparse subgraphs of the foregoing augmented graph, and requires that the lightest (or shortest in w-distance sense) path *in a sparse subgraph* between each pair of vertices has a bounded number of hops. This clearly satisfies the triangle inequality. On the other hand, the lightest path under the new notion is allowed to be heavier (wrt paths in the original graph) by a larger factor than in the original notion, and this allows for finding it within lower complexity. Later, it is shown how to translate this more crude approximation of a stronger notion to a good approximation of the original problem (SSSP).
We present a $(1+\varepsilon)$-approximate parallel algorithm for computing shortest paths in undirected graphs, achieving $\poly(\log n)$ depth and $m\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 $\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 $\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 $\poly(\log n)$-approximate single source shortest path (SSSP), Bourgain's embedding, metric tree embedding, and low diameter decomposition, all with $\poly(\log n)$ depth and $m\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 $\poly(\log n)$ depth using $m\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\poly(\log n)$.