all-pair-shortest-path

All-Pairs Shortest Paths Problem

• predecessor matrix: $\Pi =({\pi }_{ij})$
• Related: transitive-closure

Dynamic Programming Solution

• Structure of a shortest path: decomposing path $p$ to $i\stackrel{p^{\prime }}{⇝}k\to j$
  • $p^{\prime }$ is still a shortest path
  • $\delta (i,j)=\delta (i,k)+w_{kj}$

Let $l_{ij}^{(r)}$ be the minimum weight of any $i\stackrel{p}{⇝}j$ containing at most $r$ edges, we have

$$l_{ij}^{(r)}=\min \left\{l_{ij}^{(r-1)},\min \{l_{ij}^{(r-1)}+w_{kj}:1\le k\le n\}\right\}$$

The actual weight is given by

$$\delta (i,j)=l_{ij}^{(n-1)}=l_{ij}^{(n)}=l_{ij}^{(n+1)}=\dots$$

EXTEND-SHORTEST-PATHS( L(r-1), W, L(r), n )
    for i = 1 to n
        for j = 1 to n
            for k = 1 to n
                L(r)[i][j] = min( L(r)[i][j], L(r-1)[i][k] + W[k][j] )

• Invoking EXTEND-SHORTEST-PATHS $n-1$ times = $O(n^4)$
• Using repeated squaring = $O(n^3\lg n)$

Other Solutions

• Floyd-Warshall Algorithm
• Johnson’s Algorithm