Let G=(V,E) be an unweighted undirected graph on n vertices. A simple
argument shows that computing all distances in G with an additive
one-sided error of at most 1 is as hard as Boolean matrix
multiplication. Building on recent work of Aingworth, Chekuri and
Motwani, we describe an \tilde{O}(min{n^{3/2}m^{1/2},n^{7/3}) time
algorithm APASP_2 for computing all distances in G with an additive
one-sided error of at most~2. Algorithm APASP_2 is simple, easy to
implement, and faster than the fastest known matrix multiplication
algorithm. Furthermore, for every even k>2, we describe an
\tilde{O}(min{n^{2-2/(k+2)m^{2/(k+2),n^{2+2/(3k-2)}) time algorithm
APASP_k for computing all distances in G with an additive one-sided
error of at most k.

We also give an \tilde{O}(n^2) time algorithm \APASP_\infty for
producing stretch 3 estimated distances in an unweighted and
undirected graph on n vertices. No constant stretch factor was
previously achieved in \tilde{O}(n^2) time.

We say that a weighted graph F=(V,E') k-EMULATES an unweighted graph
G=(V,E) if for every u,v in V we have \delta_G(u,v) <= \delta_F(u,v)
<= \delta_G(u,v)+k. We show that every unweighted graph on n
vertices has a 2-emulator with \tilde{O}(n^{3/2}) edges and a
4-emulator with \tilde{O}(n^{4/3}) edges. These results are
asymptotically tight.

Finally, we show that any WEIGHTED undirected graph on n vertices
has a 3-spanner with \tilde{O}(n^{3/2}) edges and that such a
3-spanner can be built in \tilde{O}(mn^{1/2}) time. We also describe
an \tilde{O}(n(m^{2/3}+n)) time algorithm for estimating all
distances in a WEIGHTED undirected graph on n vertices with a stretch
factor of at most 3.

A preliminary version of this paper appeared at FOCS'96.