All pairs shortest paths in undirected graphs with integer weights

All Pairs Shortest Paths inUndirected Graphs with Integer WeightsAvi Shoshan Uri ZwickAbstractWe show that the All Pairs Shortest Paths(APSP)problemfor undirected graphs with integer edge weights taken fromthe 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 analgorithm for the APSP problem in such graphs that runsin time,where is the number of vertices in theinput graph,is the largest edge weight in the graph,and is the exponent of matrix multiplication.This improves,and also simplifies,an timealgorithm of Galil and Margalit.1.IntroductionThe All Pairs Shortest Paths(APSP)problem is one ofthe most fundamental algorithmic graph problems.TheAPSP problem for directed or undirected graphs with realweights can be solved using classical methods,intime(Dijkstra[4],Johnson[10],Fredman andTarjan[7]),or in time(Fred-man[6],Takaoka[12]).Thorup[14],[15]recently showedthat for undirected graphs with integer weights,the problemcan actually be solved in time.In the last decade,itwas shown that fast algorithms for algebraic matrix multi-plication can be used to obtain faster algorithms for solvingthe APSP problem in dense graphs with small integer edgeweights.Galil and Margalit[8],[9],and Seidel[11],ob-tained time algorithms for solving the APSP prob-lem for unweighted undirected graphs.Seidel’s algorithmis simpler.The algorithm of Galil and Margalit can be ex-tended to handle small integer weights.The currently bestupper 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 thefinite 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 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 analgorithm 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 thetime 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 herefinds the exact distances in the graph.An time algorithm for finding approximate distances with a stretch of at most, for anyfixed,is given in Zwick[16].This algorithm works even on directed graphs.An time algo-rithm forfinding 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 forfinding 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,forfinding all the distances in unweighted undirected graphs.The algorithm is a simplification 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, forfinding 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 Sections2and3find 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 graphsAn 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 USPfinds the individual bits in the binary repre-sentation of all the distances in the graph.It starts byfind-ing the most significant bits and then proceeds tofind the less significant 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 thefirst step,the algorithmfinds the most significant bits of the distances. This is quite easy to do as the most significant bit in the dis-tance is1if and only if.The most significant 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 puting the other bits in the binary representation of the distances is slightly more difficult.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 thatifotherwiseWe also let,,denote the matrices and.More generally,we let denote the ma-trix.We also let and.Thefirst 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 getwhich gives the result.If and are two sets of distances,we letLemma2.2Let and be sets of distances.Then,withrespect to any unweighted undirected graph,Proof:Thefirst three equalities are obvious.We prove thelast 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 vertexon whose distance from is.It follows thatand.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 definition of,we get thatand 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 haveProof:The lemma follows easily by induction using Lemma2.2and the following easily verified relations:Lemma2.4After stage2of algorithm USP,for every,we havealgorithm USP1.for to doend2.;;for downto0end3.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 ing the relations of Lemma2.2it is not difficult to see thatwhere in thefirst relation we assume that for every inte-ger,the function returns values in the range ,while in the second relation we assume thatit returns values in the range.By the induction hy-pothesis,.As a con-sequence we get thatThus,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 difficult 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 USPfinds 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 graphsIn this section we present an algorithm forfinding 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 assumethat,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 significant 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 whosefinite elements are taken from is a matrix whosefinite elements are from.As we do not want the range of the elements in our matrices to increase,we define the following two op-erations.If is an matrix and are two numbers, we let clip and chop be the two ma-trices such thatclip if if ifchop if otherwiseIn addition,if and are two matrices,we let ,and be the three matrices such thatifotherwiseifotherwiseifif,ifThe 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 matrixis defined in a similar way.This notation is used in stage4of WUSP.With these definitions,all the operations performed by algo-rithm WUSP are well defined,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 definitions.Let be two sets of possible distances.We defineNote that is defined exactly as in the unweighted case,while the definition of is similar,but not iden-tical to the definition of.In the previous section,we defined for every seta Boolean matrix.Here we define for every setthat satisfies certain conditions a matrix whose elements are in the range.Let,where,forand,for.We define sep,the separation of,to be.We let be an matrix such that for every we haveiffor some(the clipped zone)iffor some(the exact zone)(the infinity zone) Note that is well defined only if for everywe have.In par-ticular,we must have sep.We also let.Note thatif 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 thefinite 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 ofthe matrices and of USP.The exact definition 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 haveclipProof:Assume that,so thatand. 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 defined.To check that is well defined,we have to verify that,for.This is equivalent to the condition sep.As,is also well defined.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 nofinite 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,thenand thus, as required.If,thenand 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,andThis completes the proof that and thus clip.We next show that clip.As,we get that.Recall thatif and only if.Let.We have to show thatclip.Let be such that.If orthen we are done.We can assume,there-fore,that,.We consider again four different cases:algorithm WUSP1.for to doclipend2.for to doclipend3.clipfor downto doclip clipchopend4.for to doendFigure2.Finding all the distances in an undirected graph with weights from.Case1:andWe get that,for some,and ing both sides of the triangle inequality,we get that.is therefore in the clipped zone of and thereforeclip.Case2:andWe get that,for some,and 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 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:andWe get that,for some ,and that.As clip,we get that.Thus,.Using the other side of thetriangle 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 nowfinally 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 haveProof: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 defined above are infinite.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 havefor everyfor everyfor 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 rangewhile in the other relations,we assume that the values returned are in the ing Lemma3.2we get thatclipNote that for,we have and sep and Lemma3.2 is applicable.We next claim thatclipRecall,from the definition of,thatonly if.Consider an elementof.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 thatclipIt is easy to verify that,provided that the distance between and is at least,i.e.,if and,then.Asand as the distance condition on these two sets is satisfied, we get thatas required.Asand as the distance between and is large enough, we get thatThis 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 havefor everyProof: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 onlydistance products of matrices whosefinite 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 difficult 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 onlytime.We thus get:Theorem3.7Algorithm WUSPfinds all the distances in a weighted undirected graph whose edge weights are in the range using distance products of matrices whosefinite elements are in the range and its total running time is therefore ,where is the exponent of matrix mul-tiplication.4.Finding shortest pathsOnce all the distances in the graph were found,we canfind 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 productif for every we have and.As shown in Zwick[16],a matrix of witnesses for the distance product of two matrices withfinite 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 thatifotherwiseLet be a matrix of witnesses for the distance product .In the next lemma we show that ifthen 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,thenand by the triangle inequality,we get that.It follows therefore thatand thus if and only if,in which case.In other words,On the other hand,it is easy to see that the minimumis attained by a for which.ThusIt 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 whosefinite elements are in the range.5.Concluding remarksWe 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 antime 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 intime using the naive algorithm,or in time us-ing fast matrix multiplication algorithms.Can the distance product of two matrices with elements in the rangebe computed in time,for somefixed?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 allpairs shortest path put.Syst.Sci.,54:255–262,1997.[2] E.Cohen and U.Zwick.All-pairs small-stretch paths.InProceedings of the8th Annual ACM-SIAM Symposium on Discrete Algorithms,New Orleans,Louisiana,pages93–102,1997.[3] D.Coppersmith and S.Winograd.Matrix multiplication viaarithmetic progressions.Journal of Symbolic Computation, 9:251–280,1990.[4] E.Dijkstra.A note on two problems in connexion withgraphs.Numerische Mathematik,1:269–271,1959.[5] D.Dor,S.Halperin,and U.Zwick.All pairs almost shortestpaths.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 shortestpath problem.SIAM Journal on Computing,5:49–60,1976.[7]M.Fredman and R.Tarjan.Fibonacci heaps and their uses inimproved network optimization algorithms.Journal of the ACM,34:596–615,1987.[8]Z.Galil and O.Margalit.All pairs shortest distances forgraphs with small integer length rmation and Computation,134:103–139,1997.[9]Z.Galil and O.Margalit.All pairs shortest paths for graphswith small integer length put.Syst.Sci., 54:243–254,1997.[10] D.Johnson.Efficient algorithms for shortest paths in sparsegraphs.Journal of the ACM,24:1–13,1977.[11]R.Seidel.On the all-pairs-shortest-path problem in un-weighted undirected put.Syst.Sci.,51:400–403,1995.[12]T.Takaoka.A new upper bound on the complexity of the allpairs shortest path 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 directedgraphs–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 ofthe31th Annual ACM Symposium on Theory of Computing, Atlanta,Georgia,pages61–69,1999.。