All Pairs Shortest Paths

Given a directed, connected weighted graph $G(V,E)$, for each edge $⟨u,v⟩\in E$, a weight $w(u,v)$ is associated with the edge. The all pairs of shortest paths problem (APSP) is to find a shortest path from $u$ to $v$ for every pair of vertices $u$ and $v$ in $V$.

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

2  Algorithms for the APSP problem

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

3  Matrix Multiplication Algorithm

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($ n4 ).
Read full article from All Pairs Shortest Paths