Keywords and Synonyms
Shortest path problem; Algorithm analysis
Problem Definition
The all pairs shortest path (APSP) problem is to compute shortest paths between all pairs of vertices of a directed graph with non-negative real numbers as edge costs. Focus is given on shortest distances between vertices, as shortest paths can be obtained with a slight increase of cost. Classically, the APSP problem can be solved in cubic time of O(n 3). The problem here is to achieve a sub-cubic time for a graph with small integer costs.
A directed graph is given by \( { G=(V,E) } \), where \( { V = \{1,\ldots,n\} } \), the set of vertices, and E is the set of edges. The cost of edge \( { (i,j)\in E } \) is denoted by d ij . The (n, n)-matrix D is one whose (i, j) element is d ij . It is assumed for simplicity that \( { d_{ij} > 0 } \) and \( { d_{ii}=0 } \) for all \( { i \neq j } \). If there is no edge from i to j, let \( { d_{ij}=\infty } \). The cost, or distance, of a path is the sum of costs of...
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
Recommended Reading
Alon, N., Galil, Z., Margalit, O.: On the exponent of the all pairs shortest path problem. In: Proc. 32th IEEE FOCS, pp. 569–575. IEEE Computer Society, Los Alamitos, USA (1991). Also JCSS 54, 255–262 (1997)
Alon, N., Galil, Z., Margalit, O., Naor, M.: Witnesses for Boolean matrix multiplication and for shortest paths. In: Proc. 33th IEEE FOCS, pp. 417–426. IEEE Computer Society, Los Alamitos, USA (1992)
Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetic progressions. J. Symb. Comput. 9, 251–280 (1990)
Coppersmith, D.: Rectangular matrix multiplication revisited. J. Complex. 13, 42–49 (1997)
Huang, X., Pan, V.Y.: Fast rectangular matrix multiplications and applications. J. Complex. 14, 257–299 (1998)
Romani, F.: Shortest-path problem is not harder than matrix multiplications. Info. Proc. Lett. 11, 134–136 (1980)
Seidel, R.: On the all-pairs-shortest-path problem. In: Proc. 24th ACM STOC pp. 745–749. Association for Computing Machinery, New York, USA (1992) Also JCSS 51, 400–403 (1995)
Schönhage, A., Strassen, V.: Schnelle Multiplikation Großer Zahlen. Computing 7, 281–292 (1971)
Takaoka, T.: Sub-cubic time algorithms for the all pairs shortest path problem. Algorithmica 20, 309–318 (1998)
Zwick, U.: All pairs shortest paths using bridging sets and rectangular matrix multiplication. J. ACM 49(3), 289–317 (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer-Verlag
About this entry
Cite this entry
Takaoka, T. (2008). All Pairs Shortest Paths via Matrix Multiplication. In: Kao, MY. (eds) Encyclopedia of Algorithms. Springer, Boston, MA. https://doi.org/10.1007/978-0-387-30162-4_12
Download citation
DOI: https://doi.org/10.1007/978-0-387-30162-4_12
Publisher Name: Springer, Boston, MA
Print ISBN: 978-0-387-30770-1
Online ISBN: 978-0-387-30162-4
eBook Packages: Computer ScienceReference Module Computer Science and Engineering