__
TR00-060 | 17th August 2000 00:00
__

#### All Pairs Shortest Paths using Bridging Sets and Rectangular Matrix Multiplication

TR00-060
Authors:

Uri Zwick
Publication: 18th August 2000 10:43

Downloads: 2158

Keywords:

**Abstract:**
We present two new algorithms for solving the {\em 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 $\Ot(n^{2+\mu})$ time,

where $\mu$ satisfies the equation $\omega(1,\mu,1)=1+2\mu$ and

$\omega(1,\mu,1)$ is the exponent of the multiplication of an $n\times

n^\mu$ matrix by an $n^\mu \times n$ matrix. Currently, the best

available bounds on $\omega(1,\mu,1)$, obtained by Coppersmith,

imply that $\mu<0.575$. The running time of our algorithm is therefore

$O(n^{2.575})$. Our algorithm improves on the $\Ot(n^{(3+\omega)/2})$

time algorithm, where $\omega=\omega(1,1,1)<2.376$ is the usual exponent

of matrix multiplication, obtained by Alon, Galil and Margalit, whose

running time is only known to be $O(n^{2.688})$.

The second algorithm

solves the APSP problem {\em almost\/} exactly for directed graphs with

{\em arbitrary\/} non-negative real weights. The algorithm runs in

$\Ot((n^\omega/\eps)\log (W/\eps))$ time, where $\eps>0$ is an error

parameter and~$W$ 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+\eps$. Corresponding paths can

also be found efficiently.