## Reducing All-Pairs Shortest-Path to Matrix Multiplication

by Raimund Seidel (1992)

#### Oded's comments

The other day, I wanted to remind myself of how this celebrated
reduction (of APD to MM) works. I studied the original paper,
but felt that it puts the details before the ideas.
The wikipedia entry on
Seidel's
algorithm is even worse: It provides a Pyhton code.
So I wrote my own text, which is available HERE.

The first page of my text presents the reduction of computing
*all pairwise distances* to computing *matrix multiplication*.
Specifically, solving the problem of $n$-vertex graphs reduces
to a logarithmic number of (integer) matrix multiplications
for n-by-n matrices with entries in $\{0,1,...,n-1\}$.
The second page of my text presents the randomized reduction
of finding the first vertex on each of these shortests paths
to matrix multiplication. Here I deviate more significantly from
the original presentation and pay an extra logarithmic factor for this
(unless one employs the hint in Footnote 1).

#### Extracts from the wikipedia entry

Seidel's algorithm is an algorithm designed by Raimund Seidel in 1992
for the all-pairs-shortest-path problem for undirected, unweighted,
connected graphs. It solves the problem in $O(V^{\omega }\log V)$
expected time for a graph with V vertices,
where omega (smaller than 2.373) is the exponent in the complexity
$O(n^{\omega})$ of n-by-n n matrix multiplication.
If only the distances between each pair of vertices are sought,
the same time bound can be achieved in the worst case. ...
There is an exception to the expected running time given above
for computing the paths: if $\omega=2$ the expected running time
becomes $O(V^{2}\log ^{2}V)}$.

The core of the algorithm is a procedure that computes the length
of the shortest-paths between any pair of vertices.
This can be done in $O(V^{\omega }\log V)}$ time in the worst case

Back to
list of Oded's choices.