Timothy M. Chan's Publications: All-pairs shortest paths


More algorithms for all-pairs shortest paths in weighted graphs

In the first part of the paper, we reexamine the all-pairs shortest paths (APSP) problem and present a new algorithm with running time approaching O(n^3 log^3log n / log^2 n), which improves all known algorithms for general real-weighted dense graphs.

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-w)/(2d+4)}), where w < 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-w)/4}) = O(n^{2.844}) time) for APSP in real-vertex-weighted graphs, as well as an improved result (near O(n^{(3+w)/2}) = O(n^{2.688}) time) for the all-pairs lightest shortest path problem for small-integer-weighted graphs.


Necklaces, convolutions, and X+Y

(with
David Bremner, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Mihai Patrascu, and Perouz Taslakian)

We give subquadratic algorithms that, given two necklaces each with n beads at arbitrary positions, compute the optimal rotation of the necklaces to best align the beads. Here alignment is measured according to the l_p norm of the vector of distances between pairs of beads from opposite necklaces in the best perfect matching. We show surprisingly different results for p=1, p=2, and p=infty. For p=2, we reduce the problem to standard convolution, while for p=infty and p=1, we reduce the problem to (min,+) convolution and (median,+) convolution. Then we solve the latter two convolution problems in subquadratic time, which are interesting results in their own right. These results shed some light on the classic sorting X+Y problem, because the convolutions can be viewed as computing order statistics on the antidiagonals of the X+Y matrix. All of our algorithms run in o(n^2) time, whereas the obvious algorithms for these problems run in Theta(n^2) time.


All-pairs shortest paths for unweighted undirected graphs in o(mn) time

We revisit the all-pairs-shortest-paths problem for an unweighted undirected graph with n vertices and m edges. We present new algorithms with the following running times:

These represent the best time bounds known for the problem for all m << n^{1.376}. We also obtain a similar type of result for the diameter problem for unweighted directed graphs.


All-pairs shortest paths with real weights in O(n^3 / log n) time

We describe an O(n^3 / log n)-time algorithm for the all-pairs-shortest-paths problem for a real-weighted directed graph with n vertices. This slightly improves a series of previous, slightly subcubic algorithms by Fredman (1976), Takaoka (1992), Dobosiewicz (1990), Han (2004), Takaoka (2004), and Zwick (2004). The new algorithm is surprisingly simple and different from previous ones.


Copyright Notice

The documents contained in this directory are included by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.


Timothy M. Chan (Last updated 29 Mar 2014)