×

A new approach to all-pairs shortest paths on real-weighted graphs. (English) Zbl 1071.68084

Summary: We present a new all-pairs shortest path algorithm that works with real-weighted graphs in the traditional comparison-addition model. It runs in \(O(mn+n^2 \log \log n)\) time, improving on the long-standing bound of \(O(mn+n^2 \log n)\) derived from an implementation of Dijkstra’s algorithm with Fibonacci heaps. Here \(m\) and \(n\) are the number of edges and vertices, respectively.
Our algorithm is rooted in the so-called component hierarchy approach to shortest paths invented by Thorup for integer-weighted undirected graphs, and generalized by Hagerup to integer-weighted directed graphs. The technical contributions of this paper include a method for approximating shortest path distances and a method for leveraging approximate distances in the computation of exact ones. We also provide a simple, one line characterization of the class of hierarchy-type shortest path algorithms. This characterization leads to some pessimistic lower bounds on computing single-source shortest paths with a hierarchy-type algorithm.

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C85 Graph algorithms (graph-theoretic aspects)
68Q25 Analysis of algorithms and problem complexity
68W25 Approximation algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ahuja, R. K.; Mehlhorn, K.; Orlin, J. B.; Tarjan, R. E., Faster algorithms for the shortest path problem, J. ACM, 37, 2, 213-223 (1990) · Zbl 0696.68046
[2] Alon, N.; Galil, Z.; Margalit, O., On the exponent of the all pairs shortest path problem, J. Comput. System Sci., 54, 2, Part 1, 255-262 (1997) · Zbl 0877.68090
[3] Chazelle, B., A minimum spanning tree algorithm with inverse-Ackermann type complexity, J. ACM, 47, 6, 1028-1047 (2000) · Zbl 1094.68606
[4] Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C., Introduction to Algorithms (2001), MIT Press: MIT Press Cambridge, MA · Zbl 1047.68161
[5] Dijkstra, E. W., A note on two problems in connexion with graphs, Numer. Math., 1, 269-271 (1959) · Zbl 0092.16002
[6] E.A. Dinic, Economical algorithms for finding shortest paths in a network, in: Y.S. Popkov, B.L. Shmulyian (Eds.), Transportation Modeling Systems, Institute for system studies, Moscow, 1978, pp. 36-44.; E.A. Dinic, Economical algorithms for finding shortest paths in a network, in: Y.S. Popkov, B.L. Shmulyian (Eds.), Transportation Modeling Systems, Institute for system studies, Moscow, 1978, pp. 36-44.
[7] Fredman, M. L., New bounds on the complexity of the shortest path problem, SIAM J. Comput., 5, 1, 83-89 (1976) · Zbl 0326.68027
[8] Fredman, M. L.; Tarjan, R. E., Fibonacci heaps and their uses in improved network optimization algorithm, J. ACM, 34, 3, 596-615 (1987) · Zbl 1412.68048
[9] H.N. Gabow, A scaling algorithm for weighted matching on general graphs, in: Proc. 26th Annu. Symp. on Foundations of Computer Science (FOCS’85), 1985, pp. 90-100.; H.N. Gabow, A scaling algorithm for weighted matching on general graphs, in: Proc. 26th Annu. Symp. on Foundations of Computer Science (FOCS’85), 1985, pp. 90-100.
[10] Gabow, H. N.; Tarjan, R. E., Faster scaling algorithms for network problems, SIAM J. Comput., 18, 5, 1013-1036 (1989) · Zbl 0679.68079
[11] Galil, Z.; Margalit, O., All pairs shortest distances for graphs with small integer length edges, Inform. and Comput., 134, 2, 103-139 (1997) · Zbl 0879.68081
[12] Goldberg, A. V., Scaling algorithms for the shortest paths problem, SIAM J. Comput., 24, 3, 494-504 (1995) · Zbl 0831.68046
[13] Graham, R. L.; Yao, A. C.; Yao, F. F., Information bounds are weak in the shortest distance problem, J. ACM, 27, 3, 428-444 (1980) · Zbl 0475.68043
[14] Y. Han, Improved fast integer sorting in linear space, in: Proc. 12th Annu. ACM-SIAM Symp. on Discrete Algorithms (SODA), 2001, pp. 793-796.; Y. Han, Improved fast integer sorting in linear space, in: Proc. 12th Annu. ACM-SIAM Symp. on Discrete Algorithms (SODA), 2001, pp. 793-796. · Zbl 0992.68042
[15] Y. Han, Deterministic sorting in \(O log\); Y. Han, Deterministic sorting in \(O log\) · Zbl 1192.68196
[16] Y. Han, M. Thorup, Integer sorting in \(O log\); Y. Han, M. Thorup, Integer sorting in \(O log\)
[17] T. Hagerup, Improved shortest paths on the word RAM, in: Proc. 27th Internat. Colloq. on Automata, Languages, and Programming (ICALP’00), Lecture Notes in Computer Science, Vol. 1853, Springer, Berlin, 2000, pp. 61-72.; T. Hagerup, Improved shortest paths on the word RAM, in: Proc. 27th Internat. Colloq. on Automata, Languages, and Programming (ICALP’00), Lecture Notes in Computer Science, Vol. 1853, Springer, Berlin, 2000, pp. 61-72. · Zbl 0973.68535
[18] Johnson, D. B., Efficient algorithms for shortest paths in sparse networks, J. ACM, 24, 1, 1-13 (1977) · Zbl 0343.68028
[19] Karger, D. R.; Koller, D.; Phillips, S. J., Finding the hidden pathtime bounds for all-pairs shortest paths, SIAM J. Comput., 22, 6, 1199-1217 (1993) · Zbl 0799.68148
[20] L.R. Kerr, The effect of algebraic structure on the computational complexity of matrix multiplication, Tech. Report TR70-75, Computer Science Department, Cornell University, June 1970.; L.R. Kerr, The effect of algebraic structure on the computational complexity of matrix multiplication, Tech. Report TR70-75, Computer Science Department, Cornell University, June 1970.
[21] Kolliopoulos, S. G.; Stein, C., Finding real-valued single-source shortest paths in o \((n^3)\) expected time, J. Algorithms, 28, 1, 125-141 (1998) · Zbl 0919.68053
[22] S. Pettie, On the comparison-addition complexity of all-pairs shortest paths, in: Proc. 13th Internat. Symp. on Algorithms and Computation (ISAAC’02), 2002, pp. 32-43.; S. Pettie, On the comparison-addition complexity of all-pairs shortest paths, in: Proc. 13th Internat. Symp. on Algorithms and Computation (ISAAC’02), 2002, pp. 32-43. · Zbl 1019.68081
[23] S. Pettie, An inverse-Ackermann style lower bound for the online minimum spanning tree verification problem, in: Proc. 43rd Annu. Symp. on Found. of Computer Science (FOCS’02), 2002, pp. 155-163.; S. Pettie, An inverse-Ackermann style lower bound for the online minimum spanning tree verification problem, in: Proc. 43rd Annu. Symp. on Found. of Computer Science (FOCS’02), 2002, pp. 155-163.
[24] Pettie, S.; Ramachandran, V., An optimal minimum spanning tree algorithm, J. ACM, 49, 1, 16-34 (2002) · Zbl 1323.05124
[25] S. Pettie, V. Ramachandran, S. Sridhar, Experimental evaluation of a new shortest path algorithm, in: 4th Workshop on Algorithm Engineering and Experiments (ALENEX), 2002, pp. 126-142.; S. Pettie, V. Ramachandran, S. Sridhar, Experimental evaluation of a new shortest path algorithm, in: 4th Workshop on Algorithm Engineering and Experiments (ALENEX), 2002, pp. 126-142. · Zbl 1014.68674
[26] S. Pettie, V. Ramachandran, Computing shortest paths with comparisons and additions, in: Proc. 13th Annu. ACM-SIAM Symp. on Discrete Algorithms (SODA’02), 2002, pp. 267-276.; S. Pettie, V. Ramachandran, Computing shortest paths with comparisons and additions, in: Proc. 13th Annu. ACM-SIAM Symp. on Discrete Algorithms (SODA’02), 2002, pp. 267-276. · Zbl 1258.90101
[27] S. Pettie, V. Ramachandran, A shortest path algorithm for real-weighted undirected graphs, submitted. A preliminary version appeared in 13th ACM-SIAM Symp. on Discrete Algorithms 2002, pp. 267-276.; S. Pettie, V. Ramachandran, A shortest path algorithm for real-weighted undirected graphs, submitted. A preliminary version appeared in 13th ACM-SIAM Symp. on Discrete Algorithms 2002, pp. 267-276. · Zbl 1258.90101
[28] Seidel, R., On the all-pairs-shortest-path problem in unweighted undirected graphs, J. Comput. System Sci., 51, 3, 400-403 (1995) · Zbl 1295.05240
[29] A. Shoshan, U. Zwick, All pairs shortest paths in undirected graphs with integer weights, in: 40th Annu. Symp. on Foundations of Computer Science (FOCS), IEEE Computer Society Press, Silver Spring, MD, 1999, pp. 605-614.; A. Shoshan, U. Zwick, All pairs shortest paths in undirected graphs with integer weights, in: 40th Annu. Symp. on Foundations of Computer Science (FOCS), IEEE Computer Society Press, Silver Spring, MD, 1999, pp. 605-614.
[30] Spira, P. M.; Pan, A., On finding and updating spanning trees and shortest paths, SIAM J. Comput., 4, 3, 375-380 (1975) · Zbl 0325.05119
[31] Tarjan, R. E., A class of algorithms which require nonlinear time to maintain disjoint sets, J. Comput. System Sci., 18, 2, 110-127 (1979) · Zbl 0413.68039
[32] Takaoka, T., A new upper bound on the complexity of the all pairs shortest path problem, Inform. Process. Lett., 43, 4, 195-199 (1992) · Zbl 0763.68044
[33] Thorup, M., Undirected single-source shortest paths with positive integer weights in linear time, J. ACM, 46, 3, 362-394 (1999) · Zbl 1065.68597
[34] M. Thorup, Equivalence between priority queues and sorting, in: 43rd Annu. Symp. on Foundation of Computer Science, 2002, pp. 125-134.; M. Thorup, Equivalence between priority queues and sorting, in: 43rd Annu. Symp. on Foundation of Computer Science, 2002, pp. 125-134.
[35] M. Thorup, Integer priority queues with decrease key in constant time and the single source shortest paths problem, in: 35th Annu. ACM Symp. on Theory of Computers, 2003, pp. 149-158.; M. Thorup, Integer priority queues with decrease key in constant time and the single source shortest paths problem, in: 35th Annu. ACM Symp. on Theory of Computers, 2003, pp. 149-158. · Zbl 1192.90048
[36] van Emde Boas, P.; Kaas, R.; Zijlstra, E., Design and implementation of an efficient priority queue, Math. Systems Theory, 10, 99-127 (1977) · Zbl 0363.60104
[37] U. Zwick, Exact and approximate distances in graphs — a survey, in: Proc. 9th European Symp. on Algorithms (ESA), 2001, pp. 33-48.; U. Zwick, Exact and approximate distances in graphs — a survey, in: Proc. 9th European Symp. on Algorithms (ESA), 2001, pp. 33-48. · Zbl 1006.68543
[38] Zwick, U., All pairs shortest paths using bridging sets and rectangular matrix multiplication, J. ACM, 49, 3, 289-317 (2002) · Zbl 1326.05157
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.