All-pairs nearly 2-approximate shortest paths in o(n2poly logn) time

Let G = (V,E) be an unweighted undirected graph on |V | = n vertices and |E | = m edges. Let δ(u, v) denote the distance between vertices u, v ∈ V. An algorithm is said to compute all-pairs t-approximate shortest-paths/distances, for some t ≥ 1, if for each pair of vertices u, v ∈ V, the path/distance reported by the algorithm is not longer/greater than t · δ(u, v). This paper presents two extremely simple randomized algorithms for computing all-pairs nearly 2-approximate distances. The first algorithm requires expected O(m2/3n logn + n2) time, and for any u, v ∈ V reports distance no greater than 2δ(u, v) + 1. Our second algorithm requires expected O(n2 log3/2 n) time, and for any u, v ∈ V reports distance bounded by 2δ(u, v) + 3.