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.