Let G(V, E) be an unweighted undirected graph on |V| = n vertices. Let δ(u, v) denote the shortest distance between vertices u, v ∈ V. An algorithm is said to compute all-pairs t-approximate shortestpaths/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 randomized algorithms for computing all-pairs nearly 2-approximate distances. The first algorithm takes expected O(m2/3n log n+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) time, and for any it, v ∈ V reports distance bounded by 2δ(u, v) + 3. This paper also presents the first expected O(n 2) time algorithm to compute all-pairs 3-approximate distances. © Springer-Verlag Berlin Heidelberg 2005.