All-Pairs Shortest Paths(APSP) via fast matrix multiplication

http://www.diku.dk/PATH05/Uri1.pdf
Strassen’s nn algorithm
View each nn matrix as a 22 matrix whose elements are n/2n/2 matrices.
Apply the 22 algorithm recursively.
T(n) = 7 T(n/2) + O(n^2)
T(n) = O(nlog7/log2)=O(n2.81)

http://cs.anu.edu.au/people/Alistair.Rendell/Teaching/apac_comp3600/module4/all_pairs_shortest_paths.xhtml

1  The representation of $G$

The input is an $n\times n$ matrix $W=($ wij ).

${\displaystyle w(i,j)=\{}$ 0 if i=j the weight of the directed edge ⟨i,j⟩ if i≠j and ⟨i,j⟩∈E ∞ if i≠j and ⟨i,j⟩∉E

Algorithms for the APSP problem

• Matrix Multiplication / Repeated Squaring
• The Floyd-Warshall Algorithm
• Transitive Closure of a Graph

3  Matrix Multiplication Algorithm

http://kodu.ut.ee/~eero/PC/Lecture16.pdf

• Consider the multiplication of the weighted adjacency matrix with itself - except,

in this case, we replace the multiplication operation in matrix multiplication by

addition, and the addition operation by minimization

• Notice that the product of weighted adjacency matrix with itself returns a matrix

that contains shortest paths of length 2 between any pair of nodes

• It follows from this argument that A^n contains all shortest paths

The algorithm is based on dynamic programming, in which each major loop will invoke an operation that is very similar to matrix multiplication. Following the DP strategy, the structure of this problem is, for any two vertices $u$ and $v$,

1. if $u=v$, then the shortest path $p$ from $u$ to $v$ is 0.
   
2. otherwise, decompose $p$ into $u\to x\to v$, where $p\text{'}$ is a path from $u$ to $x$ and contains at most $k$ edges and it is the shortest path from $u$ to $x$.

A recursive solution for the APSP problem is defined. Let $d_{\mathrm{ij}}^{}$ (k) be the minimum weight of any path from $i$ to $j$ that contains at most $k$ edges.

1. If $k=0$, then
   
   

   ${\displaystyle d_{\mathrm{ij}}^{}}$ (0) ={ 0 if i=j ∞ if i≠j

   
   
2. Otherwise, for $k\ge 1$, $d_{\mathrm{ij}}^{}$ (k) can be computed from $d_{\mathrm{ij}}^{}$ (k-1) and the adjacency matrix $w$.
   $d_{\mathrm{ij}}^{}$ (k) =min{ dij (k-1) , min1≤l≤n { dil (k-1) + wlj }}= min1≤l≤n { dil (k-1) + wlj }

SPECIAL-MATRIX-MULTIPLY $(A,B)$
 1     $n$ ←  $\text{<mstyle fontstyle="italic">rows</mstyle> }[A]$
 2     $C$ ← new $n\times n$ matrix
 3    for  $i$ ←  $1$ to  $n$
 4             do for  $j$ ←  $1$ to  $n$
 5                            do  $c_{\mathrm{ij}}$ ←  $\infty$
 6                                  for  $k$ ←  $1$ to  $n$
 7                                           do  $c_{\mathrm{ij}}$ ←  $min($ cij , aik + bkj )
 .                                                    /* Here's where this algorithm */
 .                                                    /* differs from MATRIX-MULTIPLY. */
 8    return  $C$

The optimal solution can be computed by calling SPECIAL-MATRIX-MULTIPLY $($ D(k) ,W) for $1\le k\le n-2$. We only need to run to $n-2$ because that will give us $D^{(n-1)}$ giving us all the shortest path lengths of at most $n-1$ edges (you only need $n-1$ edges to connect $n$ vertices). Since SPECIAL-MATRIX-MULTIPLY is called $n-2$ times, the total running time is $O($ n^4 ).

3.1  The repeated squaring method

Since each $D^{(k)}$ matrix contains the shortest paths of at most $k$ edges, and $W$ really is $D^{(1)}$ , all we were doing in the earlier solution was going: "Given the shortests paths of at most length $k$, and the shortests paths of at most length $1$, what is the shortests paths of at most length $k+1$?"

This situation is ripe for improvement. The repeated squaring method rephrases the question to: "Given the shortests paths of at most length $k$, what is the shortests paths of at most length $k+k$?" The correctness of this approach lies in the observation that the shortests paths of at most $m$ edges is the same as the shortest paths of at most $n-1$ edges for all $m>n-1$. Thus:

$D^{(1)}$ =W
$D^{(2)}$ = W2 =W.W
$D^{(4)}$ = W4 = W2 . W2 
$:$
$D^{(}$ 2⌈log(n-1)⌉ ) = W( 2⌈log(n-1)⌉ ) = W( 2⌈log(n-1)⌉ -1) . W( 2⌈log(n-1)⌉ -1) 

Using repeated squaring, we only need to run SPECIAL-MATRIX-MULTIPLY $\lceil \log (n-1)\rceil$ times. Hence the running time of the improved matrix multiplication is $O($ n3 logn).

ALL-PAIRS-SHORTEST-PATHS $(W)$
 1     $n$ ←  $\text{<mstyle fontstyle="italic">rows</mstyle> }[W]$
 2     $D^{(1)}$ ←  $W$
 3     $m$ ←  $1$
 4    while  $m<n-1$
 5                  do  $D^{(2m)}$ ←  SPECIAL-MATRIX-MULTIPLY $($ D(m) , D(m) )
 6                         $m$ ←  $2m$
 7    return  $D^{(n)}$

3.2  Repeat Squaring Example

Figure 1: Example graph for the Repeated Squaring method.

Take the graph in Figure 1 for example. The weights for this graph in matrix form...

${\displaystyle W=(}$ 05∞∞ ∞01∞ 8∞03 2∞∞0 )= D(1)

Repeatedly squaring this gives us...

${\displaystyle D^{(1)}}$ . D(1) =( 056∞ 9014 51303 27∞0 )= D(2)

${\displaystyle D^{(2)}}$ . D(2) =( 0569 6014 51003 2780 )= D(4)

$D^{(4)}$ contains the all-pairs shortest paths. It is interesting to note that at $D^{(2)}$ , the shortest path from $2$ to $1$ is 9 using the path $⟨2,3,1⟩$. Since the final solution ( $D^{(4)}$ ) allows for up to $4$ edges to be used, a shorter path $⟨2,3,4,1⟩$ was found with a weight of 6.