All Pairs Shortest Paths in
Undirected Graphs with Integer Weights
Avi Shoshan Uri Zwick
Abstract
We show that the All Pairs Shortest Paths(APSP)problem
for undirected graphs with integer edge weights taken from
the range can be solved using only a loga-
rithmic number of distance products of matrices with ele-
ments in the range.As a result,we get an
algorithm for the APSP problem in such graphs that runs
in time,where is the number of vertices in the
input graph,is the largest edge weight in the graph,
and is the exponent of matrix multiplication.
This improves,and also simpli?es,an time
algorithm of Galil and Margalit.
1.Introduction
The All Pairs Shortest Paths(APSP)problem is one of
the most fundamental algorithmic graph problems.The
APSP problem for directed or undirected graphs with real
weights can be solved using classical methods,in
time(Dijkstra[4],Johnson[10],Fredman and
Tarjan[7]),or in time(Fred-
man[6],Takaoka[12]).Thorup[14],[15]recently showed
that for undirected graphs with integer weights,the problem
can actually be solved in time.In the last decade,it
was shown that fast algorithms for algebraic matrix multi-
plication can be used to obtain faster algorithms for solving
the APSP problem in dense graphs with small integer edge
weights.Galil and Margalit[8],[9],and Seidel[11],ob-
tained time algorithms for solving the APSP prob-
lem for unweighted undirected graphs.Seidel’s algorithm
is simpler.The algorithm of Galil and Margalit can be ex-
tended to handle small integer weights.The currently best
upper bound on,the exponent of matrix multiplication,is
,obtained by Coppersmith and Winograd[3].
If and are two matrices,then their distance product is an matrix such that,for. It is easy to see that distance products are intimately re-lated to the computation of distances.A weighted graph on vertices can be encoded as an ma-trix in which is the weight of the edge, if there is such an edge in the graph,and,other-wise.We also let,for.It is easy to see that,the-th power of with respect to distance prod-ucts,is a matrix that contains the distances between all pairs of vertices in the graph(assuming there are no negative cy-cles).The matrix can be easily computed using distance products.This is done by repeatedly squaring the matrix.Note,however,that even if the?nite elements of are taken from the small range,the el-ements of the matrices may lie in a much larger range. The last distance product,for example,may involve ele-ments as high https://www.doczj.com/doc/5510794444.html,puting distance products of matrices with such large elements is too costly.
The main contribution of this paper is the demonstration that the APSP problem for undirected graphs with integer edge weights can be solved using only a logarithmic number of distance products of matrices whose elements are taken from the same range as the original edge weights.It is easy to see that the APSP problem is at least as hard as the com-putation of a single distance product.This result,therefore, is optimal,up to a logarithmic factor.All efforts for get-ting improved algorithms for the APSP problem for undi-rected graphs with integer weights can now be devoted to obtaining improved algorithms for the computation of dis-tance products.
The range preserving reduction from the undirected APSP problem to distance products uses,in an essential way,the fact the graphs are undirected.In addition to the triangle in-equality,which states that for every three vertices and we have,and holds also in directed graphs,we also use the inverse triangle inequality, which states that for every three vertices and in an undirected graph we have.This inequality holds in undirected graphs,as, but does not hold,in general,in directed graphs.(Here denotes the distance from to in the graph.)
No range preserving reduction is known from the directed APSP problem to distance products.Improving results of Alon,Galil and Margalit[1]and Takaoka[13],the second author[16](see also[17])obtained recently an
algorithm for solving the APSP problem in directed graphs with edge weights taken from the range
.(The constants and are derived from the currently best exponents of rectangular matrix multiplications.)There is quite a large gap,there-fore,between the complexities of the currently best algo-rithms for the undirected APSP and the directed APSP prob-lems in graphs with integer edge weights.It is interesting to note,however,that the running time of both the
time algorithm for undirected graphs presented here,and the time algorithm for directed graphs presented in[16]are sub-cubic for,though for every the algorithm for undirected graphs is faster.
The time algorithm presented here?nds the exact distances in the graph.An time algorithm for ?nding approximate distances with a stretch of at most, for any?xed,is given in Zwick[16].This algorithm works even on directed graphs.An time algo-rithm for?nding approximate distances between all pairs of vertices with an additive error of at most,where is the number of edges in the graph,and an time al-gorithm for?nding all the distances with an additive error of at most are given by Cohen and Zwick[2]. These two algorithms do not use fast matrix multiplication and work again only on undirected graphs.
The rest of this paper is organized as follows.In the next section we present a simple time algorithm,called USP,for?nding all the distances in unweighted undirected graphs.The algorithm is a simpli?cation of the algorithm given for the unweighted case by Galil and Margalit[8],[9]. The algorithm computes the distances by computing their individual bits.The algorithm uses only Boolean matrix products.The resulting algorithm is quite simple. In Section3,we then present an algorithm,called WUSP, for?nding all the distances in weighted undirected graphs. The algorithm is obtained from algorithm USP by replacing the Boolean products by distance products.The algorithms described in Sections2and3?nd distances.In Section4 we show that once the distances in a graph were found,a concise description of shortest paths between all pairs of vertices in the graph can easily be found.We then end,in Section5with some concluding remarks and open prob-lems.
2.Unweighted undirected graphs
An algorithm,called USP,for solving the APSP problem for unweighted undirected graphs is given in Figure1.The algorithm receives an matrix which is the adjacency matrix of the input graph,i.e.,,if ,and,otherwise.(We assume that
.)It returns an matrix,such that is the distance from to in the graph.We assume, without loss of generality,that the graph is connected so that for every,we have
.
If and are two Boolean matrices,we let and be the matrices obtained by computing the element-wise or,or the element-wise and of the matrices and. We also let denote the matrix obtained by complement-ing all the elements of.Finally,we let denote the Boolean product of the two matrices and,i.e.,
.
Algorithm USP?nds the individual bits in the binary repre-sentation of all the distances in the graph.It starts by?nd-ing the most signi?cant bits and then proceeds to?nd the less signi?cant ones.As each distance in the graph is in the range,each distance can be represented using about bits.The algorithm is therefore composed of about steps.In the?rst step,the algorithm?nds the most signi?cant bits of the distances. This is quite easy to do as the most signi?cant bit in the dis-tance is1if and only if.The most signi?cant bits are thus easily extracted from the ma-trix that can be easily found using about Boolean matrix multiplications.In general,the algo-rithm maintains a sequence of matrices and such that and,for,where is the adjacency matrix of the https://www.doczj.com/doc/5510794444.html,puting the other bits in the binary representation of the distances is slightly more dif?cult.The way this is done is explained in the rest of this Section.
Before explaining the operation of algorithm USP in more detail and proving its correctness,we introduce some nota-tion and prove two basic lemmas.
Let be a set of possible distances.We let denote the matrix such that
if
otherwise
We also let,,denote the matrices and.More generally,we let denote the ma-trix.We also let and
.The?rst lemma we need is the triangle inequality for undirected graphs.
Lemma2.1(Triangle inequality)For every three vertices in an undirected graph we have:
Proof:The inequality holds as the concatenation of any path from to with any path from to gives a path from to.To get the other inequal-ity,we start with.As the graph is undirected,and thus
.In the same way we get
which gives the result.If and are two sets of distances,we let
Lemma2.2Let and be sets of distances.Then,with
respect to any unweighted undirected graph,
Proof:The?rst three equalities are obvious.We prove the
last relation.We begin by showing that.
Suppose that,for some.This implies that for some and.
Consider a shortest path from to.Let be the vertex
on whose distance from is.It follows that
and.Thus and,and it follows that,as required.
We next show that.Suppose that
,for some.This implies that there exists such that and
.By the triangle inequality,it follows that
.By the de?nition of,we get that
and therefore,as required. Algorithm USP is composed of three stages.The operations performed in each one of these stages are described in the following three lemmas.
Lemma2.3After stage1of algorithm USP,for every
,we have
Proof:The lemma follows easily by induction using Lemma2.2and the following easily veri?ed relations:
Lemma2.4After stage2of algorithm USP,for every
,we have
algorithm USP
1.
for to do
end
2.;
;
for downto0
end
3.
Figure1.Finding all the distances in an unweighted undirected graph.
Proof:We prove the Lemma by induction on.It is easy to verify that the claim holds for.We now show that if the claim holds for,where,then it also holds https://www.doczj.com/doc/5510794444.html,ing the relations of Lemma2.2it is not dif?cult to see that
where in the?rst relation we assume that for every inte-ger,the function returns values in the range ,while in the second relation we assume that
it returns values in the range.By the induction hy-pothesis,.As a con-sequence we get that
Thus,as required.The proof that is assigned the correct value is almost identical.All the sharp inequalities above simply have to be replaced by weak inequalities.Finally,it is easy to see that and are also assigned the correct values. This completes the proof.
It is not dif?cult to see that gives the-th bit,counting from the right,in the binary representation of the distances in the graph.Finally,in the third stage,the algorithm packs the individual bits of the distances and obtains the matrix .As a consequence we get:
Theorem2.5Algorithm USP?nds all the distances in an unweighted undirected graph using Boolean ma-trix multiplications and its total running time is therefore ,where is the exponent of matrix multi-plication.
3.Weighted undirected graphs
In this section we present an algorithm for?nding all the distances in undirected graphs with integer edge weights. The algorithm,called WUSP,is given in Figure2.The algorithm receives an matrix containing the weights of the edges in the input graph,where
.Thus,is the weight of the edge,if
,and,otherwise.We also assume
that,for.We assume that all the edge weights are taken from the range.(We can easily allow edges of weight0.We simply have to contract these edges.We cannot allow edges of negative weight.As the graph is undirected,a negative edge would immediately create a negative cycle.)
Algorithm WUSP is an extension of algorithm USP.The Boolean matrix products used in WUSP are replaced in WUSP by distance products.Recall that if and are two matrices,we let be an matrix such that,for. As shown in[1],the distance product of two matrices with elements taken from the set can be computed in time.
The distances in the input graph are all in the range.Algorithm WUSP computes the most signi?cant bits of each one of the distances, as well as the remainder that each distance leaves mod-ulo.Clearly,this gives enough information to recon-struct the distances.For simplicity we assume that is a power of2,i.e.,,for some.
The distance product of two matrices whose?nite elements are taken from is a matrix whose?nite elements are from.As we do not want the range of the elements in our matrices to increase,we de?ne the following two op-erations.If is an matrix and are two numbers, we let clip and chop be the two ma-trices such that
clip if if if
chop if otherwise
In addition,if and are two matrices,we let ,and be the three matrices such that
if
otherwise
if
otherwise
if
if,
if
The operations,and,for numerical matrices and,are“analogs”of the Boolean operations ,and for Boolean matrices and. They are used in stage3of WUSP.
Finally,if is a matrix,we let be the Boolean matrix such that,if,and
,otherwise.The Boolean matrix
is de?ned in a similar way.This notation is used in stage4of WUSP.
With these de?nitions,all the operations performed by algo-rithm WUSP are well de?ned,though we are still far from explaining what the algorithm is actually doing and why it is correct.To that end we need a few more de?nitions.
Let be two sets of possible distances.We de?ne
Note that is de?ned exactly as in the unweighted case,while the de?nition of is similar,but not iden-tical to the de?nition of.
In the previous section,we de?ned for every set
a Boolean matrix.Here we de?ne for every set
that satis?es certain conditions a matrix whose elements are in the range.
Let,where,for
and,for.We de?ne sep,the separation of,to be.We let be an matrix such that for every we have
if
for some
(the clipped zone)
if
for some
(the exact zone)
(the in?nity zone) Note that is well de?ned only if for every
we have.In par-ticular,we must have sep.We also let
.Note that
if and only if.
Algorithm WUSP tries to‘imitate’algorithm USP,using distance products instead of Boolean products.The ele-ments in the matrices whose distance product is computed will always taken from a small enough range.The and matrices of USP are replaced by the matrices of WUSP which represent distances at the range
,instead of distances in the range,as in USP. More precisely,if,
,if
,and,otherwise.Note that all the?nite elements of are in the range.The matrices are computed in stages1and2of algorithm WUSP.To ensure that the elements of are never out of the allowed range,we use the clip operation.The matri-ces and of USP are replaced by the matrices of WUSP.The matrices and of WUSP are analogs of
the matrices and of USP.The exact de?nition of the matrices,and appears in Lemma3.5.
The full version of the triangle inequality(Lemma2.1)con-tinues to hold in the weighted case.We also need the fol-lowing“window”lemma.Let be a path from to.If and are two vertices on,we let be the distance between and on.We now claim:
Lemma3.1(“Window”Lemma)Let be a path be-tween and.For each“window”
such that,there exists a vertex,such that
.
Proof:As all the edge weights in the graph are in the range ,we get that if and are two consecutive vertices on,then.The lemma follows immediately.
We now present a lemma which is an extension for the weighted case of Lemma2.2from the previous section. For simplicity,we present the Lemma only for the case ,for some,which is the case we need in or-der to prove the correctness of algorithm WUSP. Lemma3.2For every two sets of distances,such that ,where,and sep we have
clip
Proof:Assume that,so that
and. The condition sep ensures that
,for,so the intervals in the representations above are indeed disjoint.We next verify that the matrices and are well de?ned.To check that is well de?ned,we have to verify that
,for.This is equivalent to the condition sep.As
,is also well de?ned.
We next show that.The inequality clip will then follow as the clipping operation only changes entries that are below to,and values that are larger than to,while in there are no entries below,and no?nite entries larger than.We show,therefore,that for ev-ery we have. If,there is nothing to prove.We as-sume therefore that.This implies that
,for some.The proof is now broken into four different cases:
Case1:
In this case.We take and then and and thus
,as required.Case2:
Here again.In this case we choose a vertex on a shortest path from to such that
.If,we can take, otherwise,the existence of follows from the“window”lemma(Lemma3.1).As lies on a shortest path from to, we get that.As belongs to the exact zone of,we get that
.As,we get that.We consider two subcases.If,then
and thus, as required.If,then
and thus
,as required.
Case3:
In this case is in the exact zone of and so we have.We choose again a vertex on a shortest path from to such that
,and thus.As
,we get that
.Thus is in the exact zone of and we have.Thus,
Case4:
Here again.The vertex on a shortest path from to is now chosen so that
.Again.As
,we get that. Thus is still in the exact zone of so
,and
This completes the proof that and thus clip.
We next show that clip.As
,we get that
.Recall that
if and only if.
Let.We have to show that
clip.Let be such that
.If or
then we are done.We can assume,there-fore,that,.We consider again four different cases:
algorithm WUSP
1.
for to do
clip
end
2.
for to do
clip
end
3.
clip
for downto do
clip clip
chop
end
4.for to do
end
Figure2.Finding all the distances in an undirected graph with weights from.
Case1:and
We get that,for some,and https://www.doczj.com/doc/5510794444.html,ing both sides of the triangle inequality,we get that.
is therefore in the clipped zone of and therefore
clip.
Case2:and
We get that,for some
,and https://www.doczj.com/doc/5510794444.html,ing both sides of the triangle inequality,we get that
.Thus. If,then we are done.We may assume, therefore,that,and thus
.We now have to show that ,or equivalently,that. This follows from the triangle inequality
.
Case3:and This case is similar to the previous case.We get that
,for some, and https://www.doczj.com/doc/5510794444.html,ing both sides of the tri-angle inequality,we get that
.Thus.If
,then we are done.We may assume, therefore,that, and thus.We now have to show that
,or equivalently,that
.This follows from the triangle inequality.
Case4:and
We get that,for some ,and that.As clip,we get that
.Thus,
.Using the other side of the
triangle inequality,we get that
.Thus
.Thus
.If,then we are done. We may assume,therefore,that
.Thus,
This completes the proof of the lemma.
We are now?nally able to explain the operations of algo-rithm WUSP and prove its correctness.
Lemma3.3After stage1of algorithm WUSP we have clip.
Proof:In stage1,the matrix with the original edge weights of the graph is raised to the power,with entries that become larger than immediately replaced by.This clearly gives all the distances in the graph that are at most.
Lemma3.4After stage2of algorithm WUSP,for every ,we have
Proof:is initialized correctly.The claim for larger val-ues of follows by induction using Lemma3.2and the sim-ple fact that, for every.
We now let:
The sets and,as de?ned above are in?nite.We will only be interested in elements of these sets that are po-tential distances,i.e.,elements smaller than.We now have:
Lemma3.5After stage3of algorithm WUSP,we have
for every
for every
for every Proof:We use downward induction on.It is easy to check that,and are initialized correctly.We next show that if the claims hold for,where, then they also hold for.We need the following simple relations:
where,in the relations involving we assume that the function returns values in the range
while in the other relations,we assume that the values returned are in the https://www.doczj.com/doc/5510794444.html,ing Lemma3.2we get that
clip
Note that for,we have and sep and Lemma3.2 is applicable.We next claim that
clip
Recall,from the de?nition of,that
only if.Consider an element
of.If,then
,and therefore
,as required.On the other hand,if,then it is easy to check that,and therefore
,again as required.
Using very similar arguments,we get that
clip
It is easy to verify that,provided that the distance between and is at least,i.e.,if and,then.As
and as the distance condition on these two sets is satis?ed, we get that
as required.As
and as the distance between and is large enough, we get that
This relation also holds for.Finally,the operation chop extracts the entries of that belong to the exact zone.It is easy to verify that the matrix obtained is the desired.
In stage4,algorithm WUSP extracts the individual bits of the distances,and their remainder modulo,and recon-structs all the distances.
Lemma3.6After stage4of algorithm WUSP,we have
for every
Proof:For,we have if and only if.By Lemma3.5,this happens when
,as required.Special care is taken in the computation of.This is done as the claim regarding made in Lemma3.5holds only for.For we have if and only if. By the claim made in Lemma3.5regarding,a claim which holds also for,we get that if and only if,as required.For the same reason,we get that.It is easy to see that is just the-th bit in the binary representation of,where.The claim that ,for every,follows immediately.
Algorithm WUSP performs only
distance products of matrices whose?nite el-ements are either in the range(this is the case in stage1),or in the range(this is the case in stages2and3).It is not dif?cult to see that each such distance product can be reduced to a constant number of distance products of matrices with elements in the range .All other operations performed by WUSP take only
time.We thus get:
Theorem3.7Algorithm WUSP?nds all the distances in a weighted undirected graph whose edge weights are in the range using distance products of matrices whose?nite elements are in the range and its total running time is therefore ,where is the exponent of matrix mul-tiplication.
4.Finding shortest paths
Once all the distances in the graph were found,we can?nd a concise representation of shortest paths between all pairs of vertices in the graph using only three witnessed Boolean matrix products,in the unweighted case,or three witnessed distance products in the weighted case.For the unweighted case,this was shown by Seidel[11].We extend his tech-nique to the weighted case.
Let and two matrices.An matrix is said to be a matrix of witnesses for the distance product
if for every we have and
.As shown in Zwick[16],a matrix of witnesses for the distance product of two matrices with?nite elements in the range can also be found in.
Let be an undirected graph on vertices with edge weights in the range.Let be a matrix holding the edge weights of the graph,but this time with on the main diagonal,that is for any. Let be the matrix of distances in the graph.To represent the shortest paths in the graph we use a matrix,called a matrix of successors,such that for every,there is a shortest path from to that starts with the edge. Using the matrix,a shortest path from to in can be reconstructed in time which is linear in the number of edges used in this shortest path.
Let be an matrix such that
if
otherwise
Let be a matrix of witnesses for the distance product .In the next lemma we show that if
then there is a shortest path from to that starts with the edge,so we can let.
Lemma4.1If,then there is a shortest path from to that starts with the edge.
Proof:It is easy to see that if is a witness for the element,i.e.,if
,then can serve as a succes-sor for the pair,i.e.,and there is a shortest path from to that starts with the edge .We compute instead a witness for the element .We show now that if,then this witness is also a witness for the element.
Suppose that,for some, where.If,then
and by the triangle inequality,we get that
.It follows therefore that
and thus if and only if,in which case
.In other words,
On the other hand,it is easy to see that the minimum
is attained by a for which
.Thus
It follows,therefore,that any witness for is also a witness for,and vice versa.
Successors for the other pairs,i.e.,pairs for which
,or
,can be easily found using two additional distance prod-ucts.We thus get:
Theorem4.2Given the distances in a weighted undi-rected graph on vertices with edge weights in the range ,a concise description of shortest paths be-tween all pairs of vertices can be found using a constant number of distance products of matrices whose?nite elements are in the range.
5.Concluding remarks
We showed that the All Pairs Shortest Paths(APSP)prob-lem in directed graphs with edge weights taken from the range can be solved using dis-tance products of two matrices with elements in the range.As each such distance product can be computed in time,we got an
time algorithm for the APSP problem,improving a previ-ous time algorithm of Galil and Margalit [8],[9].
The obvious open problem is whether there exist better al-gorithms for computing distance products.The distance product of two matrices can be computed in
time using the naive algorithm,or in time us-ing fast matrix multiplication algorithms.Can the distance product of two matrices with elements in the range
be computed in time,for some?xed?
The algorithms given here work only for undirected graphs. Is the APSP problem for directed graphs really harder than the corresponding problem for undirected graphs?References
[1]N.Alon,Z.Galil,and O.Margalit.On the exponent of the all
pairs shortest path https://www.doczj.com/doc/5510794444.html,put.Syst.Sci.,54:255–262,1997.
[2] E.Cohen and U.Zwick.All-pairs small-stretch paths.In
Proceedings of the8th Annual ACM-SIAM Symposium on Discrete Algorithms,New Orleans,Louisiana,pages93–102,1997.
[3] D.Coppersmith and S.Winograd.Matrix multiplication via
arithmetic progressions.Journal of Symbolic Computation, 9:251–280,1990.
[4] E.Dijkstra.A note on two problems in connexion with
graphs.Numerische Mathematik,1:269–271,1959.
[5] D.Dor,S.Halperin,and U.Zwick.All pairs almost shortest
paths.In Proceedings of the37th Annual IEEE Symposium on Foundations of Computer Science,Burlington,Vermont, pages452–461,1996.Full version submitted to SIAM Jour-nal on Computing.
[6]M.Fredman.New bounds on the complexity of the shortest
path problem.SIAM Journal on Computing,5:49–60,1976.
[7]M.Fredman and R.Tarjan.Fibonacci heaps and their uses in
improved network optimization algorithms.Journal of the ACM,34:596–615,1987.
[8]Z.Galil and O.Margalit.All pairs shortest distances for
graphs with small integer length https://www.doczj.com/doc/5510794444.html,rmation and Computation,134:103–139,1997.
[9]Z.Galil and O.Margalit.All pairs shortest paths for graphs
with small integer length https://www.doczj.com/doc/5510794444.html,put.Syst.Sci., 54:243–254,1997.
[10] D.Johnson.Ef?cient algorithms for shortest paths in sparse
graphs.Journal of the ACM,24:1–13,1977.
[11]R.Seidel.On the all-pairs-shortest-path problem in un-
weighted undirected https://www.doczj.com/doc/5510794444.html,put.Syst.Sci.,51:400–403,1995.
[12]T.Takaoka.A new upper bound on the complexity of the all
pairs shortest path https://www.doczj.com/doc/5510794444.html,rmation Processing Letters, 43:195–199,1992.
[13]T.Takaoka.Subcubic cost algorithms for the all pairs short-
est path problem.Algorithmica,20:309–318,1998. [14]M.Thorup.Undirected single source shortest paths in lin-
ear time.In Proceedings of the38th Annual IEEE Sympo-sium on Foundations of Computer Science,Miami Beach, Florida,pages12–21,1997.
[15]M.Thorup.Floats,integers,and single source shortest paths.
In Proceedings of the15th Annual Symposium on Theoreti-cal Aspects of Computer Science,Paris,France,pages14–24,1998.
[16]U.Zwick.All pairs shortest paths in weighted directed
graphs–exact and almost exact algorithms.In Proceed-ings of the39th Annual IEEE Symposium on Foundations of Computer Science,Palo Alto,California,pages310–319, 1998.
[17]U.Zwick.All pairs lightest shortest paths.In Proceedings of
the31th Annual ACM Symposium on Theory of Computing, Atlanta,Georgia,pages61–69,1999.