shortest-paths/distances, for some $t\ge 1$, if for each pair of vertices $u,v\in V$, the path/distance reported by the algorithm is not longer/greater than $t\cdot \delta(u,v)$.
We present two randomized algorithms for computing all-pairs nearly
2-approximate distances. The first algorithm takes expected
$O(m^{2/3}n\log n+ n^2)$ time, and for any $u,v\in V$ reports distance no greater than $2\delta(u,v) + 1$. Our second algorithm requires
expected $O(n^2\log^{3/2})$ time, and for any $u,v\in V$ reports distance bounded by $2\delta(u,v)+3$.