  Amiri and Wargalla (2020) proved the following local-to-global theorem in
directed acyclic graphs (DAGs): if $G$ is a weighted DAG such that for each
subset $S$ of 3 nodes there is a shortest path containing every node in $S$,
then there exists a pair $(s,t)$ of nodes such that there is a shortest
$st$-path containing every node in $G$.
  We extend this theorem to general graphs. For undirected graphs, we prove
that the same theorem holds (up to a difference in the constant 3). For
directed graphs, we provide a counterexample to the theorem (for any constant),
and prove a roundtrip analogue of the theorem which shows there exists a pair
$(s,t)$ of nodes such that every node in $G$ is contained in the union of a
shortest $st$-path and a shortest $ts$-path.
  The original theorem for DAGs has an application to the $k$-Shortest Paths
with Congestion $c$ (($k,c$)-SPC) problem. In this problem, we are given a
weighted graph $G$, together with $k$ node pairs $(s_1,t_1),\dots,(s_k,t_k)$,
and a positive integer $c\leq k$. We are tasked with finding paths $P_1,\dots,
P_k$ such that each $P_i$ is a shortest path from $s_i$ to $t_i$, and every
node in the graph is on at most $c$ paths $P_i$, or reporting that no such
collection of paths exists.
  When $c=k$ the problem is easily solved by finding shortest paths for each
pair $(s_i,t_i)$ independently. When $c=1$, the $(k,c)$-SPC problem recovers
the $k$-Disjoint Shortest Paths ($k$-DSP) problem, where the collection of
shortest paths must be node-disjoint. For fixed $k$, $k$-DSP can be solved in
polynomial time on DAGs and undirected graphs. Previous work shows that the
local-to-global theorem for DAGs implies that $(k,c)$-SPC on DAGs whenever
$k-c$ is constant. In the same way, our work implies that $(k,c)$-SPC can be
solved in polynomial time on undirected graphs whenever $k-c$ is constant.
