  Let $G$ be an unweighted, undirected graph. An additive $k$-spanner of $G$ is
a subgraph $H$ that approximates all distances between pairs of nodes up to an
additive error of $+k$, that is, it satisfies $d_H(u,v) \le d_G(u,v)+k$ for all
nodes $u,v$, where $d$ is the shortest path distance. We give a deterministic
algorithm that constructs an additive $O\!\left(1\right)$-spanner with
$O\!\left(n^{4/3}\right)$ edges in $O\!\left(n^2\right)$ time. This should be
compared with the randomized Monte Carlo algorithm by Woodruff [ICALP 2010]
giving an additive $6$-spanner with $O\!\left(n^{4/3}\log^3 n\right)$ edges in
expected time $O\!\left(n^2\log^2 n\right)$.
  An $(\alpha,\beta)$-approximate distance oracle for $G$ is a data structure
that supports the following distance queries between pairs of nodes in $G$.
Given two nodes $u$, $v$ it can in constant time compute a distance estimate
$\tilde{d}$ that satisfies $d \le \tilde{d} \le \alpha d + \beta$ where $d$ is
the distance between $u$ and $v$ in $G$. Sommer [ICALP 2016] gave a randomized
Monte Carlo $(2,1)$-distance oracle of size $O\!\left(n^{5/3}\text{poly} \log
n\right)$ in expected time $O\!\left(n^2\text{poly} \log n\right)$. As an
application of the additive $O(1)$-spanner we improve the construction by
Sommer [ICALP 2016] and give a Las Vegas $(2,1)$-distance oracle of size
$O\!\left(n^{5/3}\right)$ in time $O\!\left(n^2\right)$. This also implies an
algorithm that in $O\!\left(n^2\right)$ gives approximate distance for all
pairs of nodes in $G$ improving on the $O\!\left(n^2 \log n\right)$ algorithm
by Baswana and Kavitha [SICOMP 2010].
