Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication).
In the recent past, there has been considerable progress in devising algorithms for the all-pairs shortest paths (APSP) problem running in time significantly smaller than the obvious time bound of O(n3). Unfortunately, all the new algorithms are based on fast matrix multiplication algorithms that are notoriously impractical. Our work is motivated by the goal of devising purely combinatorial algorithms that match these improved running times. Our results come close to achieving this goal, in that we present algorithms with a small additive error in the length of the paths obtained. Our algorithms are easy to implement, have the desired property of being combinatorial in nature, and the hidden constants in the running time bound are fairly small.Our main result is an algorithm which solves the APSP problem in unweighted, undirected graphs with an additive error of 2 in time $O(n^{2.5}\sqrt{\log n})$. This algorithm returns actual paths and not just the distances. In addition, we give more efficient algorithms with running time {\footnotesize $O(n^{1.5} \sqrt{k \log n} for the case where we are only required to determine shortest paths between k specified pairs of vertices rather than all pairs of vertices. The starting point for all our results is an $O(m \sqrt{n \log n})$ algorithm for distinguishing between graphs of diameter 2 and 4, and this is later extended to obtaining a ratio 2/3 approximation to the diameter in time $O(m \sqrt{n \log n} n)$. Unlike in the case of APSP, our results for approximate diameter computation can be extended to the case of  directed graphs with arbitrary positive real weights on the edges.
Introduction
Consider the problem of computing all-pairs shortest
paths (APSP) in an unweighted, undirected graph G
with n vertices and m edges. The recent work of Alon,
Galil, and Margalit [AGM91], Alon, Galil, Margalit, and
Naor [AGMN92], and Seidel [Sei92] has led to dramatic
progress in devising fast algorithms for this problem.
These algorithm are based on formulating the problem
in terms of matrices with small integer entries and using
fast matrix multiplications. They achieve a time bound
of ~
denotes the exponent in the running
time of the matrix multiplication algorithm used. The
current best matrix multiplication algorithm is due to
Coppersmith and Winograd [CW90] and has
In contrast, the naive algorithm for APSP performs
breadth-first searches from each vertex, and requires
time \Theta(nm).
Given the fundamental nature of this problem, it
is important to consider the desirability of implementing
the algorithms in practice. Unfortunately, fast matrix
multiplication algorithms are far from being practical
and suffer from large hidden constants in the running
time bound. Consequently, we adopt the view of
treating these results primarily as indicators of the existence
of efficient algorithms and consider the question
of devising a purely combinatorial algorithm for APSP
that runs in time O(n 3\Gammaffl ). The (admittedly vague)
term "combinatorial algorithm" is intended to contrast
with the more algebraic flavor of algorithms based on
fast matrix multiplication. To understand this distinc-
Department of Computer Science, Stanford University.
Email: donald@cs.stanford.edu. Supported by an NSF Graduate
Fellowship and NSF Grant CCR-9357849.
y Department of Computer Science, Stanford University.
Email: chekuri@cs.stanford.edu. Supported by an OTL grant
and NSF Grant CCR-9357849.
z Department of Computer Science, Stanford University.
Email: rajeev@cs.stanford.edu. Supported by an Alfred
P. Sloan Research Fellowship, an IBM Faculty Development
Award, an OTL grant, and NSF Young Investigator Award CCR-
9357849, with matching funds from IBM, Schlumberger Founda-
tion, Shell Foundation, and Xerox Corporation.
1 The notation ~
O(f(n)) denotes O(f(n) polylog(n)).
tion, we believe it is instructive to try and interpret the
"algebraic" algorithms in purely graph-theoretic terms
even with the use of the simpler matrix multiplication
algorithm of Strassen [Str69]. Currently, the best
known combinatorial algorithm is due to Feder and Motwani
[FM91] that runs in time O(n yielding
only a marginal improvement over the naive algorithm.
We take a step in the direction of realizing the goals
outlined above by presenting an algorithm which solves
the APSP problem with an additive error of 2 in time
O(n 2:5
log n). This algorithm returns actual paths and
not just the distances. Note that the running time
is better than ~
when the more practical matrix
multiplication algorithm of Strassen [Str69] is used
2:81) in the algorithms described earlier. Further, as
explained below, we also give slightly more efficient
algorithms (for sparse graphs) for approximating the
diameter. Our algorithms are easy to implement, have
the desired property of being combinatorial in nature,
and the hidden constants in the running time bound are
fairly small. While our results are presented only for
the case of unweighted, undirected graphs, they can be
generalized to the case of undirected graphs with small
integer edge weights; the details will be provided in the
final version of the paper.
A crucial step in the development of our result was
the shift of focus to the problem of computing the diameter
of a graph. This is the maximum over all pairs of
vertices of the shortest path distance between the ver-
tices. The diameter can be determined by computing
all-pairs shortest path (APSP) distances in the graph,
and it appears that this is the only known way to solve
the diameter problem. In fact, Fan Chung [Chu87] had
earlier posed the question of whether there is an O(n 3\Gammaffl )
algorithm for finding the diameter without resorting
to fast matrix multiplication. The situation with regard
to combinatorial algorithms for diameter is only
marginally better than in the case of APSP. Basch,
Khanna, and Motwani [BKM95] presented a combinatorial
algorithm that verifies whether a graph has diameter
2 in time O
. A slight adaptation
of this algorithm yields a boolean matrix multiplication
algorithm which runs in the same time bound, thereby
allowing us to verify that the diameter of a graph is d,
for any constant d, in O
time.
Consider the problem of devising a fast algorithm
for approximating the diameter. It is easy to estimate
the diameter within a ratio 1=2 in O(m) time: perform
a breadth-first search (BFS) from any vertex v and
let d be the depth of the BFS tree obtained; clearly,
the diameter of G lies between d and 2d. No better
approximation algorithm was known for this problem;
in fact, it was not even known how to distinguish
between graphs of diameter 2 and 4. Our first result is
an O(m
log n) algorithm for distinguishing between
graphs of diameter 2 and 4, and this is later extended
to obtaining a ratio 2=3 approximation to the diameter
in time O(m
Our work suggests several interesting directions for
future work, the most elementary being: Is there a combinatorial
algorithm running in time O(n 3\Gammaffl ) for distinguishing
between graphs of diameter 2 and 3? It is our
belief that the problem of efficiently computing the diameter
can be solved given such a decision algorithm,
and our work provides some evidence in support of this
belief. In fact, it is our view that the bottleneck in obtaining
a faster combinatorial APSP algorithm is precisely
the problem of distinguishing graphs of diameter
2 and 3. This also raises the question of whether there
is some strong equivalence between the diameter and
APSP problems, e.g., that their complexity is the same
within poly-logarithmic factors. Finally, of course, removing
the additive error from our results remains a
major open problem.
The rest of this paper is organized as follows.
We begin by presenting some definitions and useful
observations in Section 2. In Section 3, we describe
the algorithms for distinguishing between graphs of
diameter 2 and 4, and the extension to obtaining a
ratio 2=3 approximation to the diameter. Then, in
Section 4, we apply the ideas developed in estimating
the diameter to obtain the promised algorithm for an
additive approximation for APSP. Finally, in Section 5
we present an empirical study of the performance of our
algorithm for all-pairs shortest paths.
Preliminaries and a Basic Algorithm
We present some notation and a result concerning dominating
sets in graphs that underlies all our algorithms.
All definitions are with respect to some fixed undirected
graph G(V; E) with n vertices and m edges.
Definition 2.1. The distance d(u; v) between two
vertices u and v is the length of the shortest path between
them.
Definition 2.2. The diameter of a graph G is
defined to be max u;v2G d(u; v).
We will denote the diameter of the graph G by \Delta.
Definition 2.3. The k-neighborhood N k (v) of a
vertex v is the set of all vertices other than v that are
at distance at most k from v, i.e.,
The degree of a vertex v is denoted by d
Finally, we will use the notation N to
denote the set of vertices at distance at most 1 from v.
It is important to keep in mind that the set N (v)
contains not just the neighbors of v, but also includes v
itself.
Definition 2.4. For any vertex v 2 V , we denote
by b(v) the depth of a BFS tree in G rooted at the vertex
v.
Throughout this paper, we will working with a
parameter s to be chosen later that will serve as the
threshold for classifying vertices as being of low degree
or high degree. This threshold is implicit in the following
definition.
Definition 2.5. We define L(V
sg and H(V sg.
The following is a generalization of the standard
notion of a dominating set.
Definition 2.6. Given a set A ' V , a set B ' V
is a dominating set for A if and only if for each vertex
That is, for each vertex in A n B,
one of its neighbors is in B.
The following theorem underlies all our algorithms.
Theorem 2.1. There exists a dominating set for
H(V ) of size O(s \Gamma1 n log n) and such a dominating set
can be found in O(m
Remark 2.1. It is easy to see that choosing a set
of \Theta(s \Gamma1 n log n) vertices uniformly at random gives the
desired dominating set for H(V ) with high probability.
This theorem is in effect a derandomization of the
resulting randomized algorithm.
Proof. Suppose, to begin with, that H(V
then, we are interested in the standard dominating set
for the graph G. The problem of computing a minimum
dominating set for G can be reformulated as a set cover
problem, as follows: for every vertex v create a set
This gives an instance of the set cover
problem g, where the goal is to find a
minimumcardinality collection of sets whose union is V .
Given any set cover solution C ' S, the set of vertices
corresponding to the subsets in C forms a dominating set
for G of the same size as C. This is because each vertex
v occurs in one of the sets Sw 2 C, and thus is either
Fast Estimation of Diameter and Shortest Paths 3
in the dominating set itself or has a neighbor therein.
Similarly, any dominating set for G corresponds to a set
cover for S of the same cardinality.
The greedy set cover algorithm repeatedly chooses
the set that covers the most uncovered elements, and it
is known to provide a set cover of size within a factor
log n of the optimal fractional solution [Joh74, Lov75].
Since every vertex has degree at least s and therefore the
corresponding set S v has cardinality at least s, assigning
a weight of 1=s to every set in S gives a fractional set
cover of total weight (fractional size) equal to s \Gamma1 n.
Thus, the optimal fractional set cover size is O(n=s),
and the greedy set cover algorithm must then deliver a
solution of size O(s \Gamma1 n log n). This gives a dominating
set for G of the same size. If we implement the greedy
set cover algorithm by keeping the sets in buckets sorted
by the number of uncovered vertices, the algorithm can
be shown to run in time O(m).
Consider now the case where H(V Construct
a graph G adding a set of dummy vertices
)g. Every vertex in this new graph has degree s or
higher, so by the preceding argument we can construct a
dominating set for G 0 of size O(s \Gamma1 (n+s) log (n
O(s none of the new vertices in X are
connected to the vertices in H(V ), the restriction of
this dominating set to V will give a dominating set for
H(V ) of size O(s \Gamma1 n log n). Finally, the running time is
increased by the addition of the new vertices and edges,
but since the total number of edges added is at most
ns O(ns), we get the desired time bound. 2
In the rest of this paper, we will denote by D a
dominating set for H(V constructed as per this
theorem.
3 Estimating the Diameter
In this section we will develop an algorithm to find
an estimator E such that 2\Delta=3 - E - \Delta. We first
present an algorithm for distinguishing between graphs
of diameter 2 and 4. It is then shown that this algorithm
generalizes to the promised approximation algorithm.
3.1 Distinguishing Diameter 2 from 4
The basic idea behind the algorithm is rooted in the
following lemma whose proof is straight-forward.
Lemma 3.1. Suppose that G has a pair of vertices
a and b with 4. Then, the BFS tree rooted at
a vertex v 2 N (a) [ N (b) will have depth at least 3.
The algorithm, called Algorithm 2-vs-4, computes
BFS trees from a small set of vertices that is guaranteed
to contain such a vertex, and so one of these BFS trees
will certify that the diameter is more than 2.
Algorithm 2-vs-4
1. if L(V
(a) choose v 2 L(V )
(b) compute a BFS tree from each of the vertices
in N (v)
2. else
(a) compute a dominating set D for H(V
(b) compute a BFS tree from each of the vertices
in D
3. endif
4. if all BFS trees have depth 2 then return 2
return 4.
We are assuming here (and in all other algorithms)
that the sets L(V ) and D(V ) are provided as a part of
the input; otherwise, they can be computed in O(m+ns)
time.
Theorem 3.1. Algorithm 2-vs-4 distinguishes
graphs of diameter 2 and 4, and it has running time
O(ms
Proof. It is clear that the algorithm outputs 2 for
graphs of diameter 2 since in such graphs no BFS tree
can have depth exceeding 2. Assume then that G has
diameter 4 and fix any pair of vertices
that 4. We will show that the algorithm does
a BFS from a vertex v 2 N (a) [ N (b) and since, by
Lemma 3.1, the depth of the BFS tree rooted at v is at
least 3, the algorithm will output 4.
We consider the two cases that can arise in the
algorithm.
Case 1: [L(V
If either a or b belong to N (v), then there is nothing
to prove. If b(v) ? 2, then again we have nothing
to prove. Therefore, the only case that remains is
when both a and b are in N 2 (v) (see

Figure

1). Since d(a; b) - 4, all paths between a and b
have to go through a vertex in N 1 (v) which implies that
Further, since we compute a
BFS tree from each vertex in N (v), we are guaranteed
to have a BFS from a neighbor of a or b, completing the
proof. The size of N (v) is at most s, therefore the time
to compute the BFS trees is bounded by O(ms).
Case 2: [L(V
Since D is a dominating set for V , it follows
immediately that D " (N (a) [ N (b)) 6= ;, establishing
the proof of correctness. From Theorem 2.1, we have
4 Aingworth, Chekuri, Motwani
(v) has less than s nodes
a

Figure

1: Case 1 in Algorithm 2-vs-4.
log n) and this implies a bound of
O(ms log n) on the cost of computing the BFS trees
in this case. 2
Choosing
log n, we obtain the following
corollary.
Corollary 3.1. Graphs of diameter 2 and 4 can
be distinguished in O(m
log n) time.
3.2 Approximating the Diameter
The basic ideas used in Algorithm 2-vs-4 can be generalized
to estimate the diameter in general. Fix any two
vertices a and b for which \Delta, where \Delta is the
diameter of the graph. Suppose we can a find a vertex v
in N \Delta=3 (a) [N \Delta=3 (b), then it is clear that b(v) - 2\Delta=3
and we can use b(v) as our estimator. As before, we will
find a small set of vertices which is guaranteed to have
a vertex in N \Delta=3 (a) [ N \Delta=3 (b). Then, we can compute
the BFS tree from each of these vertices and use the
maximum of the depths of these trees as our estimator
E. The reason for choosing the fraction 1=3 will become
apparent in the analysis of the algorithm. In what fol-
lows, it will simplify notation to assume that \Delta=3 is
an integer; in general though, our analysis needs to be
modified to use b\Delta=3c. Also, we assume that \Delta - 3,
and it is easy to see that the case \Delta - 2 is easy to
handle separately.
A key tool in the rest of our algorithms will be the
notion of a partial-BFS defined in terms of a parameter
k. A k-partial-BFS tree is obtained by performing the
usual BFS process up to the point where exactly k
vertices (not including the root) have been visited.
Lemma 3.2. A k-partial-BFS tree can be computed
in time O(k 2 ).
Proof. The number of edges examined for each
vertex visited is bounded by k since the k-partial-BFS
process is terminated when k distinct vertices have been
examined. This implies that the total number of edges
examined is O(k 2 ), and that dominates the running
time. 2
Note that a k-partial-BFS tree contains the k
vertices closest to the root, but that this set is not
uniquely defined due to ties. Typically, k will be clear
from the context and not mentioned explicitly.
Definition 3.1. Let PBFS k (v) be the set of vertices
visited by a k-partial-BFS from v. Denote by pb(v)
the depth of the tree constructed in this fashion.
The approximation algorithm for the diameter is as
follows.
Algorithm Approx-Diameter
1. compute an s-partial-BFS tree from each vertex
in V
2. let w be the vertex with the maximum depth
3. compute a BFS tree from each vertex in
4. compute a new graph b
G from G by adding all
edges of the form (u; v) where u 2 PBFS s (v)
5. compute a dominating set D in b
G
6. compute a BFS tree from each vertex in D
7. return estimator E equal to the maximum depth
of all BFS trees from Steps 3 and 6.
The following lemmas constitute the analysis of this
algorithm.
Lemma 3.3. The dominating set D found in Step
5 is of size O(s \Gamma1 n log n).
Proof. In b
G, each vertex v 2 V is adjacent to all
vertices in PBFS s (v) with respect to the graph G.
for every vertex v, the degree
of each vertex in b
G is at least s. From Theorem 2.1,
it follows that we can find a dominating set of size
O(s
Lemma 3.4. If jN \Delta=3 (v)j - s for all
for each vertex
Proof. Consider any particular vertex v 2 V . If v is
in D, then there is nothing to prove. Otherwise, since
D is a dominating set in b
G, there is a vertex u 2 D
such that (u; v) is an edge in b
G. If (u; v) is in G, then
again we are done since u 2 N (v) ae N \Delta=3 (v). The other
possibility is that u is not a neighbor of v in G, but then
it must be the case that u 2 PBFS s (v). The condition
jN \Delta=3 (v)j - s implies that PBFS s (v) ae N \Delta=3 (v),
which in turn implies that u 2 N \Delta=3 (v), and hence
Fast Estimation of Diameter and Shortest Paths 5
The reader should notice the similarity between
the preceding lemma and Case 2 in Theorem 3.1.
Lemma 3.4 follows from the more general set cover ideas
used in the proof of Theorem 2.1 and as such it holds
even if we replace \Delta=3 by some other fraction of \Delta. The
more crucial lemma is given below.
Lemma 3.5. Let S be the set of vertices v such that
then the vertex w found in Step
2 belongs to S. In addition if b(w) ! 2\Delta=3, then for
every vertex v, PBFS s (w) " N \Delta=3 (v) 6= ;.
Proof. It can be verified that for any vertex u 2 S,
conversely, for any vertex v in V n S,
\Delta=3. From this we can conclude that if S is
nonempty, then the vertex of largest depth belongs to
S.
Also, for each vertex u 2 S, we must have
N \Delta=3 (u) ae PBFS s (u). If b(w) ! 2\Delta=3 then every
vertex is within a distance 2\Delta=3 of w. From this and
the fact that N \Delta=3 (w) ae PBFS s (w), it follows that
The proof of the above lemma makes clear the
reason why our estimate is only within 2=3 of the
diameter. Essentially, we need to ensure that the \Delta=k
neighborhood of w intersects the \Delta=k neighborhood of
every other vertex. This can happen only if b(w) is
sufficiently small. If it is not small enough, we want b(w)
itself to be a good estimator. Balancing these conditions
gives us and the ratio 2=3.
Theorem 3.2. Algorithm Approx-Diameter gives
an estimate E such that 2\Delta=3 -
O(ms ms ns 2 ). Choosing
log n
gives a running time of O(m
Proof. The analysis is partitioned into two cases.
Let a and b be two vertices such that \Delta.
Case 1: [For all vertices v, jN \Delta=3 (v)j - s.]
If either a or b is in D, we are done. Otherwise
from the proof of Lemma 3.4, the set D has a vertex
(b). Since in Step 6 we compute
BFS trees from each vertex in D, one of these is v and
b(v) is the desired estimator.
Case 2: [There exists a vertex v 2 V such that
Let w be the vertex in Step 2. If b(w) - 2\Delta=3,
b(w) is our estimator and we are done. Otherwise from
Lemma 3.5, PBFS s (w) has a vertex v 2 N \Delta=3 (a) [
N \Delta=3 (b). Since in Step 3 we compute BFS trees from
each vertex in PBFS s (w), one of these is v and b(v) is
the desired estimator.
The running time is easy to analyze. Each partial-
BFS in Step 1 takes at most O(s 2
thus, the total time spent on Step 1 is O(ns 2 ). Step
2 can be implemented in O(n) time. In Step 3, we
compute BFS trees from s vertices, which requires a
total of O(ms) time. The time required in Step 4 is
dominated by the time required to compute the partial-
BFS trees in Step 1. Theorem 2.1 implies that Step 5
requires only O(n 2 (note that the graph b
G
could have many more edges than m). By Lemma 3.3,
Step 6 takes O(ms time. Finally, the cost
of Step 7 is dominated by the cost of computing the
various BFS trees in Steps 3 and 6. The running time is
dominated by the cost of Steps 1, 3, and 6, and adding
the bounds for these gives the desired result. 2
Additive Factor Approximations
It is possible to determine not only the diameter, but the
all-pairs shortest path distances to within an additive
error of 2. The basic idea is that a dominating set,
since it contains a neighbor of every vertex in the graph,
must contain a vertex that is within distance 1 of any
shortest path. Since we can only find a small dominating
set for vertices in H(V ), we have to treat L(V ) vertices
differently, but their low degree allows us to manage
with only a partial-BFS, which we can combine with
the information we have gleaned from the dominating
set.
Algorithm Approx-APSP
Comment: Define G[L(V )] to be the subgraph of
G induced by L(V ).
1. initialize all entries in the distance matrix b
d to
infinity
2. compute a dominating set D for H(V ) of size
3. compute a BFS tree from each vertex v 2 D, and
update b
d with the shortest path lengths for v so
obtained
4. compute a BFS tree in G[L(V )] for each vertex
d with the shortest path
lengths for v so obtained
5. for all u; do
6. return b
d as the APSP matrix, and its largest entry
as the diameter.

Figure

2 illustrates the idea behind this algorithm.
6 Aingworth, Chekuri, Motwani
The actual shortest path
The path computed in step 5
HI LO
The BFS for a node in LO (step
The BFS for a node in D (Step
A graph with HI, LO, D labeled

Figure

2: Illustration of Algorithm Approx-APSP.
Theorem 4.1. In Algorithm Approx-APSP, for all
vertices , the distances returned in b
d satisfy
2. Further, the algorithm
can be modified to produce paths of length b
d rather
than merely returning the approximate distances. This
algorithm runs in time O(n choosing
log n gives a running time of O(n 2:5
log n).
Proof. We first show that the algorithm can be
easily modified to return actual paths rather than only
the distances. To achieve this, in Steps 3 and 4 we can
associate with each updated entry in the matrix the
path from the BFS tree used for the update. In Step 5,
we merely concatenate the two paths from Step 3 the
sum of whose lengths determine the minimum value of
d.
For a vertex u, it is clear that the shortest path
distance to any vertex v 2 V that is returned cannot be
smaller than the correct values, since they correspond
to actual paths. To see that they differ by no more than
2, we need to consider three cases:
Case 1: [u 2 D]
In this case, the BFS tree from v is computed in
Step 3 and so clearly the distances returned are correct.
Case 2:
By the definition of D, it must be the case that u
has a neighbor w in D. Clearly, the distances from
u and w to any other vertex cannot differ by more
than 1, and the distances from w are always correct
as per Case 1. The assignment in Step 6 guarantees
2.
Case 3: [u 2 L(V )]
Fix any shortest path from u to v. Suppose that
the path from u to v is entirely contained in L(V ); then,
d(u; v) is set correctly in Step 4. Otherwise, the path
must contain a vertex w 2 H(V ). If w is contained in
D, then the correct distance is computed as per Case 1.
Finally, if w 2 H(V )nD, then D contains a neighbor x of
Clearly, in Step 6, one of the possibilities considered
will involve a path from u to x and a path from x to v.
Since the distances involving x are correctly computed
in Step 3, this means that b
2.
Finally, we analyze the running time of this algo-
rithm. Step 1 requires only O(n 2 ) time, and Theorem
2.1 implies that we can perform Step 2 in the stated
time bound. Step 3 requires ms \Gamma1 n log n for computing
the BFS trees. Step 4 may compute as many as \Omega\Gamma n)
BFS trees, but G[L(V )] only has O(ns) edges and so this
requires only O(n 2 s) time. Finally, Step 5 takes all
vertex pairs, and compares them against the s
vertices in D. This implies the desired time bound. 2
Although the error in this algorithm is 2, it can be
improved for the special case of distinguishing diameter
2 from 4 based on the following two observations.
Fact 4.1. If u 2 H(V ) is at distance \Delta from some
vertex v, then b
Proof. Consider w, the vertex that dominates u. If
the algorithm were to have set b
5 of the algorithm would imply b
d is
exact for vertices in D, this is not possible. 2
Fact 4.2. Whenever the algorithm reports for
some 2, we can verify this in
time O(ns) per vertex.
Thus, by performing a verification for each of the
vertices that report distance over 2, we can improve
Algorithm Approx-APSP so that it always performs
as well as the diameter approximation algorithms
of the previous section. The first fact also appears to
be useful in bringing the diameter error down to 1, but
unfortunately, the vertices in L(V ) cannot be handled
as easily for larger diameters.
5 Experimental Results
To evaluate the usefulness of our algorithm, we ran
it on two families of graphs and compared the results
against a carefully coded algorithm based on
breadth-first searches. The algorithm Approx-APSP
was tweaked with the following heuristic improvement
to Step 5 that avoids many needless iterations: when a
node has a neighbor in D, then we copy the distances of
its neighbor (since they can differ by at most 1). This
algorithm (called Fast Approx-APSP) occasionally has
a higher fraction of incorrect entries, but seems to be the
fastest way to solve the all-pairs shortest path problem.
Fast Estimation of Diameter and Shortest Paths 7
Approx-APSP Fast Approx-APSP Approx-APSP Fast Approx-APSP
speedup speedup accuracy accuracy
GB Median 0:59 3:95 0:69 0:53
GB Average 2:44 10:18 0:72 0:47
GB Standard Deviation 0:24 1:73 0:16 0:13
RG Median 0:52 5:30 0:39 0:51
RG Average 0:63 4:75 0:39 0:55
RG Standard Deviation 0:23 1:70 0:14 0:12

Table

1: Summary of Experimental Results
The first family of graphs were random graphs
from the G n;m model [Bol85], which are graphs chosen
uniformly at random from those with n vertices and
m edges. In our experiments, we chose random graphs
with n ranging from 10 to 1000, and 2m=n 2 ranging
from 0:03 to 0:90. On these graphs, Fast Approx-APSP
runs about 5 times faster than the BFS implementation,
and about half of the distances are off by one.
The second family of graphs come from the Stanford
GraphBase [Knu93]. We tested all of the connected,
undirected graphs from Appendix C in Knuth [Knu93],
ignoring edge weights. This is a very heterogeneous
family of graphs, including graphs representing highway
connections for American cities, athletic schedules, 5-
letter English words, and expander graphs, as well as
more combinatorial graphs. Thus the results here are
quite indicative of practical performance. Although the
BFS-based algorithm runs fastest for certain subfamilies
of the GraphBase, Fast Approx-APSP outperformed all
other algorithms overall.
The results are summarized in Table 1. In the table,
GB and RG refer to GraphBase and random graphs, re-
spectively. The speedup numbers indicate the inverse of
the ratio of the execution time of the algorithms to that
of the carefully coded BFS algorithm. The accuracy
refers to the ratio of the total number of exact entries
in the distance matrix to the total number of entries in
the matrix. In both of these families, the accuracy of
Approx-APSP could be improved by subtracting 1 in
Step 5. This did not seem necessary given that the BFS
approach performed about as fast as Approx-APSP, and
that Fast- Approx APSP performed faster with roughly
50% accuracy. The numbers indicate that for general
graphs where an additive factor error is acceptable, Fast
Approx-APSP is the algorithm of choice, and for more
specific families of graphs, the parameters can be adjusted
for even better performance.

Acknowledgements

We are grateful to Noga Alon for his comments and
suggestions, and to Nati Linial for helpful discussions.
Thanks also to Michael Goldwasser, David Karger,
Sanjeev Khanna, and Eric Torng for their comments.



--R

On the exponent of the all pairs shortest path problem.
for Boolean Matrix Multiplication and for Shortest Paths.
On Diameter Verification and Boolean Matrix Multiplication.
Random Graphs.
Diameters of Graphs: Old Problems and New Results.
Matrix multiplication via arithmetic progressions.
Clique partitions
Approximation algorithms for combinatorial problems.

On the ratio of optimal integral and
On the all-pairs-shortest-path problem
Gaussian elimination is not optimal.
--TR

--CTR
David Eppstein , Joseph Wang, Fast approximation of centrality, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.228-229, January 07-09, 2001, Washington, D.C., United States
Mattias Andersson , Joachim Gudmundsson , Christos Levcopoulos, Approximate distance oracles for graphs with dense clusters, Computational Geometry: Theory and Applications, v.37 n.3, p.142-154, August, 2007
Toms Feder , Rajeev Motwani , Liadan O'Callaghan , Chris Olston , Rina Panigrahy, Computing shortest paths with uncertainty, Journal of Algorithms, v.62 n.1, p.1-18, January, 2007
Alan P. Sprague, O(1) query time algorithm for all pairs shortest distances on permutation graphs, Discrete Applied Mathematics, v.155 n.3, p.365-373, February, 2007
Mikkel Thorup , Uri Zwick, Approximate distance oracles, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.183-192, July 2001, Hersonissos, Greece
Joachim Gudmundsson , Christos Levcopoulos , Giri Narasimhan , Michiel Smid, Approximate distance oracles for geometric graphs, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.828-837, January 06-08, 2002, San Francisco, California
Michael Elkin , Jian Zhang, Efficient algorithms for constructing (1+,, )-spanners in the distributed and streaming models, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada
Mikkel Thorup , Uri Zwick, Approximate distance oracles, Journal of the ACM (JACM), v.52 n.1, p.1-24, January 2005
Joan Feigenbaum , Sampath Kannan , Andrew McGregor , Siddharth Suri , Jian Zhang, Graph distances in the streaming model: the value of space, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
Feodor F. Dragan, Estimating all pairs shortest paths in restricted graph families: a unified approach, Journal of Algorithms, v.57 n.1, p.1-21, September 2005
Surender Baswana , Telikepalli Kavitha , Kurt Mehlhorn , Seth Pettie, New constructions of (, )-spanners and purely additive spanners, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
Mikkel Thorup , Uri Zwick, Spanners and emulators with sublinear distance errors, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.802-809, January 22-26, 2006, Miami, Florida
Surender Baswana , Sandeep Sen, Approximate distance oracles for unweighted graphs in expected O(n2) time, ACM Transactions on Algorithms (TALG), v.2 n.4, p.557-577, October 2006
Timothy M. Chan, All-pairs shortest paths for unweighted undirected graphs in o(mn) time, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.514-523, January 22-26, 2006, Miami, Florida
Rezaul Alam Chowdhury , Vijaya Ramachandran, External-memory exact and approximate all-pairs shortest-paths in undirected graphs, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
Surender Baswana , Sandeep Sen, A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs, Random Structures & Algorithms, v.30 n.4, p.532-563, July 2007
All pairs shortest paths using bridging sets and rectangular matrix multiplication, Journal of the ACM (JACM), v.49 n.3, p.289-317, May 2002
shortest paths;diameter;matrix multiplication