  A long series of recent results and breakthroughs have led to faster and
better distributed approximation algorithms for single source shortest paths
(SSSP) and related problems in the CONGEST model. The runtime of all these
algorithms, however, is $\tilde{\Omega}(\sqrt{n})$, regardless of the network
topology, even on nice networks with a (poly)logarithmic network diameter $D$.
While this is known to be necessary for some pathological networks, most
topologies of interest are arguably not of this type.
  We give the first distributed approximation algorithms for shortest paths
problems that adjust to the topology they are run on, thus achieving
significantly faster running times on many topologies of interest. The running
time of our algorithms depends on and is close to $Q$, where $Q$ is the quality
of the best shortcut that exists for the given topology. While $Q =
\tilde{\Theta}(\sqrt{n} + D)$ for pathological worst-case topologies, many
topologies of interest have $Q = \tilde{\Theta}(D)$, which results in near
instance optimal running times for our algorithm, given the trivial $\Omega(D)$
lower bound.
  The problems we consider are as follows: (1) an approximate shortest path
tree and SSSP distances, (2) a polylogarithmic size distance label for every
node such that from the labels of any two nodes alone one can determine their
distance (approximately), and (3) an (approximately) optimal flow for the
transshipment problem.
  Our algorithms have a tunable tradeoff between running time and approximation
ratio. Our fastest algorithms have an arbitrarily good polynomial approximation
guarantee and an essentially optimal $\tilde{O}(Q)$ running time. On the other
end of the spectrum, we achieve polylogarithmic approximations in $\tilde{O}(Q
\cdot n^{\epsilon})$ rounds for any $\epsilon > 0$.
