All pairs shortest paths using bridging sets and rectangular matrix multiplication

ABSTRACT

We present two new algorithms for solving the All Pairs Shortest Paths (APSP) problem for weighted directed graphs. Both algorithms use fast matrix multiplication algorithms.The first algorithm solves the APSP problem for weighted directed graphs in which the edge weights are integers of small absolute value in Õ(n^2+μ) time, where μ satisfies the equation ω(1, μ, 1) = 1 + 2μ and ω(1, μ, 1) is the exponent of the multiplication of an n × n^μ matrix by an n^μ × n matrix. Currently, the best available bounds on ω(1, μ, 1), obtained by Coppersmith, imply that μ < 0.575. The running time of our algorithm is therefore O(n^2.575). Our algorithm improves on the &Otilede;(n^(3c+ω)/2) time algorithm, where ω = ω(1, 1, 1) < 2.376 is the usual exponent of matrix multiplication, obtained by Alon et al., whose running time is only known to be O(n^2.688).The second algorithm solves the APSP problem almost exactly for directed graphs with arbitrary nonnegative real weights. The algorithm runs in Õ((n^ω/&epsis;) log(W/&epsis;)) time, where &epsis; > 0 is an error parameter and W is the largest edge weight in the graph, after the edge weights are scaled so that the smallest non-zero edge weight in the graph is 1. It returns estimates of all the distances in the graph with a stretch of at most 1 + &epsis;. Corresponding paths can also be found efficiently.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: D. Aingworth , C. Chekuri , P. Indyk , R. Motwani, Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication), SIAM Journal on Computing, v.28 n.4, p.1167-1181, Aug. 1999 [doi>10.1137/S0097539796303421]
• 3: Noga Alon , Zvi Galil , Oded Margalit, On the exponent of the all pairs shortest path problem, Journal of Computer and System Sciences, v.54 n.2, p.255-262, April 1997 [doi>10.1006/jcss.1997.1388]
• 4: Alon, N., and Naor, M. 1996. Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions. Algorithmica 16, 434--449.
• 5: Burgisser, P., Clausen, M., and Shokrollahi, M. A. 1997. Algebraic Complexity Theory. Springer-Verlag, New York.
• 6: Chvátal, V. 1979. A greedy heuristic for the set-covering problem. Math. Oper. Res. 4, 233--235.
• 7: Edith Cohen , Uri Zwick, All-pairs small-stretch paths, Journal of Algorithms, v.38 n.2, p.335-353, Feb. 2001 [doi>10.1006/jagm.2000.1117]
• 8: Don Coppersmith, Rectangular matrix multiplication revisited, Journal of Complexity, v.13 n.1, p.42-49, March 1997 [doi>10.1006/jcom.1997.0438]
• 9: Don Coppersmith , Shmuel Winograd, Matrix multiplication via arithmetic progressions, Journal of Symbolic Computation, v.9 n.3, p.251-280, March 1990 [doi>10.1016/S0747-7171(08)80013-2]
• 10: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 11: Dijkstra, E. W. 1959. A note on two problems in connexion with graphs. Num. Math. 1, 269--271.
• 12: Dorit Dor , Shay Halperin , Uri Zwick, All-Pairs Almost Shortest Paths, SIAM Journal on Computing, v.29 n.5, p.1740-1759, March 2000 [doi>10.1137/S0097539797327908]
• 13: Fredman, M. L. 1976. New bounds on the complexity of the shortest path problem. SIAM J. Comput. 5, 49--60.
• 14: Michael L. Fredman , Robert Endre Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, Journal of the ACM (JACM), v.34 n.3, p.596-615, July 1987 [doi>10.1145/28869.28874]
• 15: Zvi Galil , Oded Margalit, Witnesses for Boolean matrix multiplication and for transitive closure, Journal of Complexity, v.9 n.2, p.201-221, June 1993 [doi>10.1006/jcom.1993.1014]
• 16: Zvi Galil , Oded Margalit, All pairs shortest distances for graphs with small integer length edges, Information and Computation, v.134 n.2, p.103-139, May 1, 1997 [doi>10.1006/inco.1997.2620]
• 17: Zvi Galil , Oded Margalit, All pairs shortest paths for graphs with small integer length edges, Journal of Computer and System Sciences, v.54 n.2, p.243-254, April 1997 [doi>10.1006/jcss.1997.1385]
• 18: M. R. Henzinger , V. King, Fully dynamic biconnectivity and transitive closure, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.664, October 23-25, 1995
• 19: Xiaohan Huang , Victor Y. Pan, Fast rectangular matrix multiplication and applications, Journal of Complexity, v.14 n.2, p.257-299, June 1, 1998 [doi>10.1006/jcom.1998.0476]
• 20: Donald B. Johnson, Efficient Algorithms for Shortest Paths in Sparse Networks, Journal of the ACM (JACM), v.24 n.1, p.1-13, Jan. 1977 [doi>10.1145/321992.321993]
• 21: David R. Karger , Daphne Koller , Steven J. Phillips, Finding the hidden path: time bounds for all-pairs shortest paths, SIAM Journal on Computing, v.22 n.6, p.1199-1217, Dec. 1993 [doi>10.1137/0222071]
• 22: Lovász, L. 1975. On the ratio of optimal integral and fractional covers. Disc. Math. 13, 383--390.
• 23: McGeoch, C. C. 1995. All-pairs shortest paths and the essential subgraph. Algorithmica 13, 426--461.
• 24: Victor Pan, How to multiply matrices faster, Springer-Verlag New York, Inc., New York, NY, 1984
• 25: Schönhage, A., and Strassen, V. 1971. Schnelle multiplikation grosser zahlen. Computing 7, 281--292.
• 26: Raimund Seidel, On the all-pairs-shortest-path problem in unweighted undirected graphs, Journal of Computer and System Sciences, v.51 n.3, p.400-403, Dec. 1995 [doi>10.1006/jcss.1995.1078]
• 27: Avi Shoshan , Uri Zwick, All Pairs Shortest Paths in Undirected Graphs with Integer Weights, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.605, October 17-18, 1999
• 28: Tadao Takaoka, A new upper bound on the complexity of the all pairs shortest path problem, Information Processing Letters, v.43 n.4, p.195-199, Sept. 28, 1992 [doi>10.1016/0020-0190(92)90200-F]
• 29: Takaoka, T. 1998. Subcubic cost algorithms for the all pairs shortest path problem. Algorithmica 20, 309--318.
• 30: Mikkel Thorup, Undirected single-source shortest paths with positive integer weights in linear time, Journal of the ACM (JACM), v.46 n.3, p.362-394, May 1999 [doi>10.1145/316542.316548]
• 31: Mikkel Thorup, Floats, integers, and single source shortest paths, Journal of Algorithms, v.35 n.2, p.189-201, May 2000 [doi>10.1006/jagm.2000.1080]
• 32: Jeffrey D. Ullman , Mihalis Yannakakis, High probability parallel transitive-closure algorithms, SIAM Journal on Computing, v.20 n.1, p.100-125, Feb. 1991 [doi>10.1137/0220006]
• 33: Yuval, G. 1976. An algorithm for finding all shortest paths using N2.81 infinite-precision multiplications. Inf. Proc. Lett. 4, 155--156.
• 34: Uri Zwick, All Pairs Shortest Paths in weighted directed graphs ? exact and almost exact algorithms, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.310, November 08-11, 1998
• 35: Uri Zwick, All pairs lightest shortest paths, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.61-69, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301271]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Theory

Keywords:
Matrix multiplication, shortest paths