Lecture 18 - Notes

March 14, 2016

Shortest Path Algorithms Continued

Floyd-Warshall Algorithm

definition: To find the shortest path between all pairs d[n][n] and make a shortest distance matrix. Let $d_{ij}^{(k)}$ be the shortest path from $i$ to $j$ passing through vertices, $1,2,...,k$. The algorithm states,

$$\begin{aligned} d_{ij}^{(k)} = \min(d_{ij}^{(k-1)},d_{ik}^{(k-1)} + d_{kj}^{(k-1)}) \end{aligned}$$