Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models

(SSSP) problem. As a consequence, we improve prior work by obtaining the following results: 1. Broadcast congest model: (1+ε)-approximate SSSP using O ̃(ε^(−O(1))(√n+D)) rounds, where
D is the (hop) diameter of the network.
2. Broadcast congested clique model: (1+ε)-approximate shortest transshipment and SSSP using
O ̃(ε^(−O(1))) rounds.
3. Multipass streaming model: (1+ε)-approximate shortest transshipment and SSSP using O ̃(n) space and O ̃(ε^(−O(1))) passes.
The previously fastest SSSP algorithms for these models leverage sparse hop sets. We bypass the hop set construction; computing a spanner is sufficient with our method. The above bounds assume non-negative integer edge weights that are polynomially bounded in n; for general non- negative weights, running times scale with the logarithm of the maximum ratio between non-zero weights. In case of asymmetric costs for pushing flow through an edge in opposite directions, running times scale with the maximum ratio between the costs of both directions over all edges.