  Low congestion shortcuts, introduced by Ghaffari and Haeupler (SODA 2016),
provide a unified framework for global optimization problems in the congest
model of distributed computing. Roughly speaking, for a given graph $G$ and a
collection of vertex-disjoint connected subsets $S_1,\ldots, S_\ell \subseteq
V(G)$, $(c,d)$ low-congestion shortcuts augment each subgraph $G[S_i]$ with a
subgraph $H_i \subseteq G$ such that: (i) each edge appears on at most $c$
subgraphs (congestion bound), and (ii) the diameter of each subgraph $G[S_i]
\cup H_i$ is bounded by $d$ (dilation bound). It is desirable to compute
shortcuts of small congestion and dilation as these quantities capture the
round complexity of many global optimization problems in the congest model. For
$n$-vertex graphs with constant diameter $D=O(1)$, Elkin (STOC 2004) presented
an (implicit) shortcuts lower bound with
$c+d=\widetilde{\Omega}(n^{(D-2)/(2D-2)})$. A nearly matching upper bound,
however, was only recently obtained for $D \in \{3,4\}$ by Kitamura et al.
(DISC 2019).
  In this work, we resolve the long-standing complexity gap of shortcuts in
constant diameter graphs, originally posed by Lotker et al. (PODC 2001). We
present new shortcut constructions which match, up to poly-logarithmic terms,
the lower bounds of Das-Sarma et al. As a result, we provide improved and
existentially optimal algorithms for several network optimization tasks in
constant diameter graphs, including MST, $(1+\epsilon)$-approximate minimum
cuts and more.
