All pairs shortest paths using bridging sets and rectangular matrix multiplication
By Uri Zwick. JACM, 2000
355 citations recorded by the source corpus.
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 <i>Õ</i>(<i>n</i><sup>2+μ</sup>) time, where μ satisfies the equation ω(1, μ, 1) = 1 + 2μ and ω(1, μ, 1) is the exponent of the multiplication of an <i>n</i> × <i>n</i><sup>μ</sup> matrix by an <i>n</i><sup>μ</sup> × <i>n</i> matrix. Currently, the best available bounds on ω(1, μ, 1), obtained by Coppersmith, imply that μ < 0.575. The running time of our algorithm is therefore <i>O</i>(<i>n</i><sup>2.575</sup>). Our algorithm improves on the <i>&Otilede;</i>(<i>n</i><sup>(3c+ω)/2</sup>) 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 <i>O</i>(<i>n</i><sup>2.688</sup>).The second algorithm solves the APSP problem <i>almost</i> exactly for directed graphs with <i>arbitrary</i> nonnegative real weights. The algorithm runs in Õ((<i>n</i><sup>ω</sup>/&epsis;) log(<i>W</i>/&epsis;)) time, where &epsis; > 0 is an error parameter and <i>W</i> 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 + &epsis;. Corresponding paths can also be found efficiently.
Subfields: Computational Theory and Mathematics, Computer Graphics and Computer-Aided Design
View Paper: https://www.semanticscholar.org/paper/eec92e7994b43ff8aedc1986a5049e7c31997fbc
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Theory and Mathematics
- Kyriakos G. Vamvoudakis
- Frank L. Lewis
- Ryan Williams
- Virginia Vassilevska Williams
- Gregory R. Hudas
- Raphael Yuster
- Mikkel Thorup
- Uri Zwick
In Computer Graphics and Computer-Aided Design
Citations in the corpus
- Subcubic Equivalences between Path, Matrix and Triangle Problems (2010, background): “Unfortunately, the latter algorithm is pseudopolynomial (exponential in the bit complexity) and can only be used to efficiently solve APSP in special cases such as when the weights in the graph are small [56, 77], or when the weights are on the nodes instead of the edges [15, 16].”
- Approximate distance oracles (2001, background): “Time Reference 1 O(1) O(m) O(n2) O(m) O(mn) 0 [Thorup 1999] [Thorup 1999] 1 + E O(1) O(n2) O(n.) [Zwick 2002] 2 O(1) O(n2) O(m1/2n3/2) [Cohen and Zwick 2001] 7/3 O(1) O(n2) O(n7/3) [Cohen and Zwick 2001] 3 O(1) O(1) O(1) O(n2) O(m1/3n + n2/m1/3) O(n3/2) O(n2) O(m2/3n) O(mn1/2) [Cohen and Zwick…”
- A new algorithm for optimal 2-constraint satisfaction and its implications (2005, methodology): “When weights are independent of m and n, it is possible to use an approximate all-pairs shortest paths algorithm of [30] to get a (1 + )-approximation in roughly O(nm31.”
- Fast sparse matrix multiplication (2004, methodology): “Fast matrix multiplication algorithms can be used, for example, to obtain fast algorithms for .nding simple cycles in graphs [Alon et al. 1995, 1997; Yuster and Zwick 2004], for .nding small cliques and other small subgraphs [Ne.set.ril and Poljak 1985], for .nding shortest paths [Seidel 1995; Sh”
- Multi-agent differential graphical games (2011, background): “It is usual in graph theory to select small edge weights (eij ≤ emax where emax is a relatively small positive number), shortest path graph problems based on scaling (Goldberg, 1995) and fast matrix multiplication (Zwick, 2002) have running times that depend on the edge weights, and therefore yield ”