Let $G(V,E)$ be an undirected weighted graph with $|V|=n, |E|=m$.
Recently Thorup and Zwick introduced a remarkable data-structure
that stores all-pairs approximate distance information implicitly in $o(n^2)$
space, and yet answers any approximate distance query in {\em constant}
time, hence the name {\em approximate distance oracle}. Given an integer $k>1$,
a $(2k-1)$-approximate distance oracle requires $O(kn^{1+1/k})$ space
and answers a $(2k-1)$-approximate distance query in $O(k)$ time.
Thorup and Zwick showed that a $(2k-1)$-approximate distance oracle can
be computed in $O(kmn^{1/k})$ time, and posed the following question :
{\em Can $(2k-1)$-approximate distance oracle be computed in $\tilde{O}(n^2)$
time ?}
In this paper, we answer their question in affirmative for unweighted graphs.
We present an algorithm that computes $(2k-1)$-approximate distance oracle
for a given unweighted graph in $\tilde{O}(n^2)$ time.
One of the new ideas used in the improved algorithm also leads to the first
linear time algorithm for computing an optimal size $(2,1)$-spanner of an
unweighted graph.