  The All-Pairs Shortest Paths (APSP) problem is one of the fundamental
problems in theoretical computer science. It asks to compute the distance
matrix of a given $n$-vertex graph. We revisit the classical problem of
maintaining the distance matrix under a fully dynamic setting undergoing vertex
insertions and deletions with a fast worst-case running time and efficient
space usage.
  Although an algorithm with amortized update-time $\tilde O(n ^ 2)$ has been
known for nearly two decades [Demetrescu and Italiano, STOC 2003], the current
best algorithm for worst-case running time with efficient space usage runs is
due to [Gutenberg and Wulff-Nilsen, SODA 2020], which improves the space usage
of the previous algorithm due to [Abraham, Chechik, and Krinninger, SODA 2017]
to $\tilde O(n ^ 2)$ but fails to improve their running time of $\tilde O(n ^
{2 + 2 / 3})$. It has been conjectured that no algorithm in $O(n ^ {2.5 -
\epsilon})$ worst-case update time exists. For graphs without negative cycles,
we meet this conjectured lower bound by introducing a Monte Carlo algorithm
running in randomized $\tilde O(n ^ {2.5})$ time while keeping the $\tilde O(n
^ 2)$ space bound from the previous algorithm. Our breakthrough is made
possible by the idea of ``hop-dominant shortest paths,'' which are shortest
paths with a constraint on hops (number of vertices) that remain shortest after
we relax the constraint by a constant factor.
