Abstract
We design a faster algorithm for the all-pairs shortest path problem under the RAM model, based on distance matrix multiplication (DMM). Specifically we improve the best known time complexity of O(n 3(loglog n/log n)1/2) to T(n)=O(n 3(loglog n)2/log n). We extend the algorithm to a parallel algorithm for DMM, whose time complexity is O(log n) and number of processors is T(n)/log n. As an application, we show how to speed up the algorithm for the maximum subarray problem.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Akl, S.: The design and analysis of parallel algorithms. Prentice-Hall, Englewood Cliffs (1989)
Alon, N., Galil, Margalit: On the Exponent of the All Pairs Shortest Path Problem. Jour. Comp. Sys. Sci. 54(2), 255–262 (1997)
Bentley, J.: Programming Pearls - Perspective on Performance, Comm. ACM 27, 1087–1092 (1984)
Fredman, M.: New bounds on the complexity of the shortest path problem. SIAM Jour. Computing 5, 83–89 (1976)
Han, Y., Pan, V.Y., Reif, J.H.: Efficient parallel algorithms for computing all pair shortest paths in directed graphs. Algorithmica 17, 399–415 (1997)
Horowitz, E., Sahni, S., Rajasekaran, S.: Computer Algorithms. Computer Science Press, Rockville (1998)
Moffat, A., Takaoka, T.: An all pairs shortest path algorithm with O(n2 log n) expected time. SIAM Jour. Computing (1987)
Takaoka, T.: A New Upper Bound on the complexity of the all pairs shortest path problem. Info. Proc. Lett. 43, 195–199 (1992)
Takaoka, T.: Subcubic algorithms for the all pairs shortest path problem. Algorithmica 20, 309–318 (1998)
Takaoka, T.: Subcubic algorithms for the maximum subarray probelm. In: Proc. Computing: Australasian Theory Symposium (CATS 2002), pp. 189-198 (2002)
Tamaki, H., Tokuyama, T.: Algorithms for the Maximum Subarray Problem Based on Matrix Multiplicarion. In: Proceedings of the 9th SODA (Symposium on Discrete Algorithms), pp. 446-452 (1998)
Zwick, U.: All pairs shortest paths in weighted directed graphs - exact and almost exact algorithms. In: 39th FOCS, pp. 310-319 (1998)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Takaoka, T. (2004). A Faster Algorithm for the All-Pairs Shortest Path Problem and Its Application. In: Chwa, KY., Munro, J.I.J. (eds) Computing and Combinatorics. COCOON 2004. Lecture Notes in Computer Science, vol 3106. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-27798-9_31
Download citation
DOI: https://doi.org/10.1007/978-3-540-27798-9_31
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-22856-1
Online ISBN: 978-3-540-27798-9
eBook Packages: Springer Book Archive