## All-Pairs Shortest Paths Problem - _predecessor matrix_: $\Pi = (\pi_{ij})$ - Related: _[[transitive-closure]]_ ## [[dp|Dynamic Programming]] Solution - Structure of a shortest path: decomposing path $p$ to $i \overset{p'}\leadsto k \to j$ - $p'$ is still a shortest path - $\delta(i, j) = \delta(i, k) + w_{kj}$ Let $l_{ij}^{(r)}$ be the minimum weight of any $i\overset{p}\leadsto 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|Floyd-Warshall Algorithm]] - [[johnson|Johnson's Algorithm]]