More algorithms for all-pairs shortest paths in weighted graphs

ABSTRACT

In the first part of the paper, we reexamine the all-pairsshortest paths (APSP) problem and present a newalgorithm with running time approaching O(n³/log²n), which improves all known algorithms for general real-weighted dense graphs andis perhaps close to the best result possible without using fast matrix multiplication, modulo a few log log n factors.

In the second part of the paper, we use fast matrix multiplication to obtain truly subcubic APSP algorithms for a large class of "geometrically weighted" graphs, where the weight of an edge is a function of the coordinates of its vertices. For example, for graphs embedded in Euclidean space of a constant dimension d, we obtain a time bound near O(n^{3-(3-Ω)/(2d+4)}), where Ω < 2.376 ; in two dimensions, this is O(n^2.922). Our framework greatly extends the previously considered case of small-integer-weighted graphs, and incidentally also yields the first truly subcubic result (near O(n^3-(3-Ω)/4)=O(n^2.844) time) forAPSP in real-vertex-weighted graphs, as well as an improved result (near O(n^(3+Ω)/2)=O(n^2.688) time) for the all-pairs lightest shortest path problem for small-integer-weighted graphs.

REFERENCES

• 1: P. K. Agarwal and J. Matousek. On range searching with semialgebraic sets. J. DCG (11) 393--418. 1994.
• 2: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 3: Susanne Albers , Torben Hagerup, Improved parallel integer sorting without concurrent writing, Information and Computation, v.136 n.1, p.25-51, July 10, 1997 [doi>10.1006/inco.1997.2632]
• 4: Noga Alon , Zvi Galil , Oded Margalit, On the exponent of the all pairs shortest path problem, Proceedings of the 32nd annual symposium on Foundations of computer science, p.569-575, September 1991, San Juan, Puerto Rico
• 5: Noga Alon , Raphael Yuster , Uri Zwick, Color-coding, Journal of the ACM (JACM), v.42 n.4, p.844-856, July 1995 [doi>10.1145/210332.210337]
• 6: V. L. Arlazarov, E. C. Dinic, M. A. Kronrod, and I. A. Faradzev. On economical construction of the transitive closure of a directed graph. J Soviet Math. Dokl. 11 1209--1210 1970.
• 7: Timothy M. Chan, Dynamic subgraph connectivity with geometric applications, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509911]
• 8: T. M. Chan. All-pairs shortest paths with real weights in O(n³/log n) time. In LNCS WADS 9th 3608 318--324 2005. Algorithmica, to appear.
• 9: Timothy M. Chan, All-pairs shortest paths for unweighted undirected graphs in o(mn) time, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.514-523, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109614]
• 10: Timothy M. Chan , Alon Efrat, Fly cheaply: on the minimum fuel consumption problem, Journal of Algorithms, v.41 n.2, p.330-337, November 2001 [doi>10.1006/jagm.2001.1189]
• 11: B. Chazelle. Cuttings. In Handbook of Data Structures and Applications, CRC Press, pages 25.1--25. 10, 2005.
• 12: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 13: A. Czumaj and A. Lingas. Finding a heaviest triangle is not harder than matrix multiplication. In SODA 18th, 2007.
• 14: W. Dobosiewicz. A more efficient algorithm for the min-plus multiplication. Int. J. Computer Math. 32 49--60 1990.
• 15: Tomás Feder , Rajeev Motwani, Clique partitions, graph compression and speeding-up algorithms, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.123-133, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103424]
• 16: M. L. Fredman. New bounds on the complexity of the shortest path problem. J SIComp 5 49--60 1976.
• 17: Yijie Han, Improved algorithm for all pairs shortest paths, Information Processing Letters, v.91 n.5, p.245-250, 15 September 2004 [doi>10.1016/j.ipl.2004.05.006]
• 18: Yijie Han, An O(n³ (loglogn/logn)^5/4) time algorithm for all pairs shortest paths, Proceedings of the 14th conference on Annual European Symposium, p.411-417, September 11-13, 2006, Zurich, Switzerland [doi>10.1007/11841036_38]
• 19: H. Kaplan, N. Rubin, M. Sharir, and E. Verbin. Counting colors in boxes. In SODA 18th, 2007.
• 20: Haim Kaplan , Micha Sharir , Elad Verbin, Colored intersection searching via sparse rectangular matrix multiplication, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA [doi>10.1145/1137856.1137866]
• 21: Vladlen Koltun, Almost tight upper bounds for vertical decompositions in four dimensions, Journal of the ACM (JACM), v.51 n.5, p.699-730, September 2004 [doi>10.1145/1017460.1017461]
• 22: J. Matousek. Computing dominances in Eⁿ. J. IPL 38 277--278 1991.
• 23: Jiří Matoušek, Efficient partition trees, Discrete & Computational Geometry, v.8 n.3, p.315-334, 1992 [doi>10.1007/BF02293051]
• 24: K. Mulmuley. Computational Geometry: An Introduction Through Randomized Algorithms. Prentice-Hall, Englewood Cliffs, N.J., 1994.
• 25: Giri Narasimhan , Michiel Smid, Approximating the Stretch Factor of Euclidean Graphs, SIAM Journal on Computing, v.30 n.3, p.978-989, 2000 [doi>10.1137/S0097539799361671]
• 26: Seth Pettie, A new approach to all-pairs shortest paths on real-weighted graphs, Theoretical Computer Science, v.312 n.1, p.47-74, 26 January 2004 [doi>10.1016/S0304-3975(03)00402-X]
• 27: Seth Pettie , Vijaya Ramachandran, A Shortest Path Algorithm for Real-Weighted Undirected Graphs, SIAM Journal on Computing, v.34 n.6, p.1398-1431, 2005 [doi>10.1137/S0097539702419650]
• 28: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 29: Robert Sedgewick , Jeffrey Scott Vitter, Shortest paths in Euclidean graphs, Algorithmica, v.1 n.1, p.31-48, Jan. 1986 [doi>10.1007/BF01840435]
• 30: Raimund Seidel, On the all-pairs-shortest-path problem, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.745-749, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129784]
• 31: 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
• 32: 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]
• 33: T. Takaoka. A faster algorithm for the all-pairs shortest path problem and its application. In LNCS COCOON 10th 3106 278--289 2004.
• 34: Virginia Vassilevska , Ryan Williams, Finding a maximum weight triangle in n^3-Δ time, with applications, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132550]
• 35: V. Vassilevska, R. Williams, and R. Yuster. Finding the smallest H-subgraph in real weighted graphs and related problems. In LNCS ICALP 33rd 4051 262--273 2006.
• 36: 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]
• 37: All pairs shortest paths using bridging sets and rectangular matrix multiplication, Journal of the ACM (JACM), v.49 n.3, p.289-317, May 2002 [doi>10.1145/567112.567114]
• 38: Uri Zwick, A Slightly Improved Sub-Cubic Algorithm for the All Pairs Shortest Paths Problem with Real Edge Lengths, Algorithmica, v.46 n.2, p.181-192, October 2006 [doi>10.1007/s00453-005-1199-1]

INDEX TERMS

General Terms:
Algorithms, Theory

Keywords:
computational geometry, graph algorithms, matrix multiplication, shortest paths