All-pairs nearly 2-approximate shortest paths in 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 an expected O(m2/3nlogn+n2) time, and for any u,v∈V reports a distance no greater than 2δ(u,v)+1. Our second algorithm requires an expected O(n2log3/2n) time, and for any u,v∈V reports a distance bounded by 2δ(u,v)+3.