Uri Zwick
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 Õ(n2+μ) 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(n2.575). Our algorithm improves on the Õ(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(n2.688).The second algorithm solves the APSP problem almost exactly for directed graphs with arbitrary nonnegative real weights. The algorithm runs in Õ((nω/ϵ) log(W/ϵ)) time, where ϵ > 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 + ϵ. Corresponding paths can also be found efficiently.
- Aho, A. V., Hopcroft, J. E., and Ullman, J. D. 1974. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, Mass. Google Scholar
- Aingworth, D., Chekuri, C., Indyk, P., and Motwani, R. 1999. Fast estimation of diameter and shortest paths (without matrix multiplication). SIAM J. Comput. 28, 1167--1181. Google Scholar
- Alon, N., Galil, Z., and Margalit, O. 1997. On the exponent of the all pairs shortest path problem. J. Comput. Syst. Sci. 54, 255--262. Google Scholar
- Alon, N., and Naor, M. 1996. Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions. Algorithmica 16, 434--449.Google Scholar
- Burgisser, P., Clausen, M., and Shokrollahi, M. A. 1997. Algebraic Complexity Theory. Springer-Verlag, New York. Google Scholar
- Chvátal, V. 1979. A greedy heuristic for the set-covering problem. Math. Oper. Res. 4, 233--235.Google Scholar
- Cohen, E., and Zwick, U. 2001. All-pairs small-stretch paths. J. Algorithms 38, 335--353. Google Scholar
- Coppersmith, D. 1997. Rectangular matrix multiplication revisited. J. Complex. 13, 42--49. Google Scholar
- Coppersmith, D., and Winograd, S. 1990. Matrix multiplication via arithmetic progressions. J. Symb. Comput. 9, 251--280. Google Scholar
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. 2001. Introduction to Algorithms, 2nd ed. The MIT Press, Cambridge, Mass. Google Scholar
- Dijkstra, E. W. 1959. A note on two problems in connexion with graphs. Num. Math. 1, 269--271.Google Scholar
- Dor, D., Halperin, S., and Zwick, U. 2000. All pairs almost shortest paths. SIAM J. Comput. 29, 1740--1759. Google Scholar
- Fredman, M. L. 1976. New bounds on the complexity of the shortest path problem. SIAM J. Comput. 5, 49--60.Google Scholar
- Fredman, M. L., and Tarjan, R. E. 1987. Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM 34, 596--615. Google Scholar
- Galil, Z., and Margalit, O. 1993. Witnesses for Boolean matrix multiplication. J. Complex. 9, 201--221. Google Scholar
- Galil, Z., and Margalit, O. 1997. All pairs shortest distances for graphs with small integer length edges. Inf. Comput. 134, 103--139. Google Scholar
- Galil, Z., and Margalit, O. 1997b. All pairs shortest paths for graphs with small integer length edges. J. Comput. Syst. Sci. 54, 243--254. Google Scholar
- Henzinger, M. R., and King, V. 1995. Fully dynamic biconnectivity and transitive closure. In Proceedings of the 36th Annual IEEE Symposium on Foundations of Computer Science (Milwaukee, Wis). IEEE Computer Society Press, Los Alamitos, Calif., pp. 664--672. Google Scholar
- Huang, X., and Pan, V. Y. 1998. Fast rectangular matrix multiplications and applications. J. Complex. 14, 257--299. Google Scholar
- Johnson, D. B. 1977. Efficient algorithms for shortest paths in sparse graphs. J. ACM 24, 1--13. Google Scholar
- Karger, D. R., Koller, D., and Phillips, S. J. 1993. Finding the hidden path: Time bounds for all-pairs shortest paths. SIAM J. Comput. 22, 1199--1217. Google Scholar
- Lovász, L. 1975. On the ratio of optimal integral and fractional covers. Disc. Math. 13, 383--390.Google Scholar
- McGeoch, C. C. 1995. All-pairs shortest paths and the essential subgraph. Algorithmica 13, 426--461.Google Scholar
- Pan, V. 1985. How to Multiply Matrices Faster. Lecture Notes in Computer Science, Vol. 179. Springer-Verlag, New York. Google Scholar
- Schönhage, A., and Strassen, V. 1971. Schnelle multiplikation grosser zahlen. Computing 7, 281--292.Google Scholar
- Seidel, R. 1995. On the all-pairs-shortest-path problem in unweighted undirected graphs. J. Comput. Syst. Sci. 51, 400--403. Google Scholar
- Shoshan, A., and Zwick, U. 1999. All pairs shortest paths in undirected graphs with integer weights. In Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science (New York, New York). IEEE Computer Society Press, Los Alamitos, Calif., pp. 605--614. Google Scholar
- Takaoka, T. 1992. A new upper bound on the complexity of the all pairs shortest path problem. Inf. Proc. Lett. 43, 195--199. Google Scholar
- Takaoka, T. 1998. Subcubic cost algorithms for the all pairs shortest path problem. Algorithmica 20, 309--318.Google Scholar
- Thorup, M. 1999. Undirected single-source shortest paths with positive integer weights in linear time. J. ACM 46, 362--394. Google Scholar
- Thorup, M. 2000. Floats, integers, and single source shortest paths. J. Algorithms 35, 189--201. Google Scholar
- Ullman, J. D., and Yannakakis, M. 1991. High-probability parallel transitive-closure algorithms. SIAM J. Comput. 20, 100--125. Google Scholar
- Yuval, G. 1976. An algorithm for finding all shortest paths using N2.81 infinite-precision multiplications. Inf. Proc. Lett. 4, 155--156.Google Scholar
- Zwick, U. 1998. All pairs shortest paths in weighted directed graphs---Exact and almost exact algorithms. In Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science (Palo Alto, Calif.). IEEE Computer Society Press, Los Alamitos, Calif., pp. 310--319. Google Scholar
- Zwick, U. 1999. All pairs lightest shortest paths. In Proceedings of the 31th Annual ACM Symposium on Theory of Computing (Atlanta, Ga.). ACM, New York, pp. 61--69. Google Scholar
Index Terms
- All pairs shortest paths using bridging sets and rectangular matrix multiplication
Recommendations
All-pairs shortest paths for unweighted undirected graphs in o(mn) time
We revisit the all-pairs-shortest-paths problem for an unweighted undirected graph with n vertices and m edges. We present new algorithms with the following running times:
{ O(mn/log n) if m > n log n log log log n O(mn log log n/log n) if m > n log log ...
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 ...
All-pairs shortest paths with a sublinear additive error
We show that, for every 0 ≤ p ≤ 1, there is an O(n2.575−p/(7.4−2.3p))-time algorithm that given a directed graph with small positive integer weights, estimates the length of the shortest path between every pair of vertices u, v in the graph to within an ...
Reviews
Jerzy W. Jaromczyk
The fundamental problem of finding the shortest paths between all pairs of vertices in a weighted graph, the “all pairs shortest path” (APSP), is studied in this paper. APSP is practically important, and is particularly tantalizing due to the lack of nontrivial lower bounds. The author presents new algorithms that follow a series of recent papers, in which strong upper bounds related to the cost of square matrix multiplications have been found for directed graphs whose edge weights are integers with small absolute values. Thanks to clever use of rectangular instead of square matrices, new, improved upper bounds are derived for the above, and for &egr;-approximation APSP problems. The latter algorithm solves the APSP problem almost exactly (with a stretch of, at most, 1 + &egr;) for directed graphs with arbitrary nonnegative real weights, and has the best known upper bound at this time. These theoretically important results provide new insight into APSP. Online Computing Reviews Service
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments