  We study the fully dynamic All-Pairs Shortest Paths (APSP) problem in
undirected edge-weighted graphs. Given an $n$-vertex graph $G$ with
non-negative edge lengths, that undergoes an online sequence of edge insertions
and deletions, the goal is to support approximate distance queries and
shortest-path queries. We provide a deterministic algorithm for this problem,
that, for a given precision parameter $\epsilon$, achieves approximation factor
$(\log\log n)^{2^{O(1/\epsilon^3)}}$, and has amortized update time
$O(n^{\epsilon}\log L)$ per operation, where $L$ is the ratio of longest to
shortest edge length. Query time for distance-query is
$O(2^{O(1/\epsilon)}\cdot \log n\cdot \log\log L)$, and query time for
shortest-path query is $O(|E(P)|+2^{O(1/\epsilon)}\cdot \log n\cdot \log\log
L)$, where $P$ is the path that the algorithm returns. To the best of our
knowledge, even allowing any $o(n)$-approximation factor, no adaptive-update
algorithms with better than $\Theta(m)$ amortized update time and better than
$\Theta(n)$ query time were known prior to this work. We also note that our
guarantees are stronger than the best current guarantees for APSP in
decremental graphs in the adaptive-adversary setting.
