  Given a directed weighted graph $G=(V,E)$ undergoing vertex insertions
\emph{and} deletions, the All-Pairs Shortest Paths (APSP) problem asks to
maintain a data structure that processes updates efficiently and returns after
each update the distance matrix to the current version of $G$. In two
breakthrough results, Italiano and Demetrescu [STOC '03] presented an algorithm
that requires $\tilde{O}(n^2)$ \emph{amortized} update time, and Thorup showed
in [STOC '05] that \emph{worst-case} update time $\tilde{O}(n^{2+3/4})$ can be
achieved. In this article, we make substantial progress on the problem. We
present the following new results:
  (1) We present the first deterministic data structure that breaks the
$\tilde{O}(n^{2+3/4})$ worst-case update time bound by Thorup which has been
standing for almost 15 years. We improve the worst-case update time to
$\tilde{O}(n^{2+5/7}) = \tilde{O}(n^{2.71..})$ and to $\tilde{O}(n^{2+3/5}) =
\tilde{O}(n^{2.6})$ for unweighted graphs.
  (2) We present a simple deterministic algorithm with $\tilde{O}(n^{2+3/4})$
worst-case update time ($\tilde{O}(n^{2+2/3})$ for unweighted graphs), and a
simple Las-Vegas algorithm with worst-case update time $\tilde{O}(n^{2+2/3})$
($\tilde{O}(n^{2 + 1/2})$ for unweighted graphs) that works against a
non-oblivious adversary. Both data structures require space $\tilde{O}(n^2)$.
These are the first exact dynamic algorithms with truly-subcubic update time
\emph{and} space usage. This makes significant progress on an open question
posed in multiple articles [COCOON'01, STOC '03, ICALP'04, Encyclopedia of
Algorithms '08] and is critical to algorithms in practice [TALG '06] where
large space usage is prohibitive. Moreover, they match the worst-case update
time of the best previous algorithms and the second algorithm improves upon a
Monte-Carlo algorithm in a weaker adversary model with the same running time
[SODA '17].
