  Single Source Shortest Paths ($\textrm{SSSP}$) is among the most well-studied
problems in computer science. In the incremental (resp. decremental) setting,
the goal is to maintain distances from a fixed source in a graph undergoing
edge insertions (resp. deletions). A long line of research culminated in a
near-optimal deterministic $(1 + \varepsilon)$-approximate data structure with
$m^{1 + o(1)}$ total update time over all $m$ updates by Bernstein, Probst
Gutenberg and Saranurak [FOCS 2021]. However, there has been remarkably little
progress on the exact $\textrm{SSSP}$ problem beyond Even and Shiloach's
algorithm [J. ACM 1981] for unweighted graphs. For weighted graphs, there are
no exact algorithms beyond recomputing $\textrm{SSSP}$ from scratch in
$\widetilde{O}(m^2)$ total update time, even for the simpler Single-Source
Single-Target Shortest Path problem ($\textrm{stSP}$). Despite this lack of
progress, known (conditional) lower bounds only rule out algorithms with
amortized update time better than $m^{1/2 - o(1)}$ in dense graphs.
  In this paper, we give a tight (conditional) lower bound: any partially
dynamic exact $\textrm{stSP}$ algorithm requires $m^{2 - o(1)}$ total update
time for any sparsity $m$. We thus resolve the complexity of partially dynamic
shortest paths, and separate the hardness of exact and approximate shortest
paths, giving evidence as to why no non-trivial exact algorithms have been
obtained while fast approximation algorithms are known.
  Moreover, we give tight bounds on the complexity of combinatorial algorithms
for several path problems that have been studied in the static setting since
early sixties: Node-weighted shortest paths (studied alongside edge-weighted
shortest paths), bottleneck paths (early work dates back to 1960), and earliest
arrivals (early work dates back to 1958).
