Approximate Distance Oracles with Improved Preprocessing Time

Given an undirected graph $G$ with $m$ edges, $n$ vertices, and non-negative edge weights, and given an integer $k\ge 1$, we show that for some universal constant $c$, a $(2k-1)$-approximate distance oracle for $G$ of size $O(kn^{1 + 1/k})$canbeconstructedin$O(\sqrt km + kn^{1 + c/\sqrt k})$ time and can answer queries in $O(k)$ time. We also give an oracle which is faster for smaller $k$. Our results break the quadratic preprocessing time bound of Baswana and Kavitha for all $k\ge 6$ and improve the $O(km{n}^{1\mathrm{/}k})$ time bound of Thorup and Zwick except for very sparse graphs and small $k$. When $m = \Omega(n^{1 + c/\sqrt k})$and$k = O(1)$, our oracle is optimal w.r.t.\ both stretch, size, preprocessing time, and query time, assuming a widely believed girth conjecture by Erd\H{o}s.