All Pairs Shortest Paths and Matrix multiplication

Here, an "All pairs shortest paths" algorithm, that runs in $O(|V|^3log|V|)$ time is presented.

Pseudo-Code:


      EXTEND-SHORTEST-PATH$(L,W)$

1. $n = L.row$
2. $L'$ is a new $n \times n$ matrix
3. for $i$ from 1 to $n$
4.       for $j$ from 1 to $n$
5.             $l_{ij}' = \infty$
6.             for $k$ from 1 to $n$
7.                   $l_{ij}' = min(l_{ij}',l_{ik}+w_{kj})$
8. return L'

Explanation:

Here we assume that each matrix object has it's rows saved in it as an attribute as $row$. We basically try every path from $i$(source vertex) through $k$ (intermediate vertex) to $j$ (destination vertex).
This algorithm runs in $O(n^3)$ time.

NOTE: This algorithm is similar to Matrix multiplication.

Here $L$ is actually $L^{m-1}$ for some $m$, and $L'$ is $L^m$. We don't use $m$ in the algorithm to remove any dependence on $m$.

EXTEND-SHORTEST-PATH is used by:

      SLOW-ALL-PAIRS-SHORTEST-PATHS$(W)$

1. $n = W.rows$
2. $L^{(1)} = W$
3. for $m=2$ to $n-1$
4.       let $L^{(m)}$ be a new $n \times n$ matrix
5.       $L^{(m)} =$EXTEND-SHORTEST-PATHS$(L^{(m-1)},W)$
6. return $L^{(n-1)}$

And this will run in $O(n^4)$ time.

This can be reduced by seeing the fact that just like matrix multiplication, EXTEND-SHORTEST-PATH is also associative. Thus $\text{EXTEND-SHORTEST-PATH}(L^{(3)},W) = \text{EXTEND-SHORTEST-PATH}(L^{(2)},L^{(2)})$.

Therefore, we can just do repeated squaring. That is, squaring until we get a $L^{m}$, where $m \geq n-1$. We know that $\delta(i,j) = l_{ij}^{n-1} = l_{ij}^n=l_{ij}^{n+1}=...$ because the maximum number of edges in the shortest path between two vertices is $|V|-1 = n-1$. Since $l_{ij}$ denotes the minimum weight of any path between $i$ and $j$, that contains at most $m$ edges.

Thus:

      FAST-ALL-PAIRS-SHORTEST-PATHS$(W)$

1. $n=W.rows$
2. $L^{(1)} = W$
3. $m=1$
4. while $m< n-1$
5.       let $L^{(2m)}$ be a new $n \times n$ matrix
6.       $L^{(2m)}=$EXTEND-SHORTEST-PATHS$(L^{(m)},L^{(m)})$
7.       $m=2m$
8. return $L^{(m)}$

This obviously runs in $O(n^3logn)$ time. Cool!