floyd-warshall

The Floyd-Warshall Algorithm

• Number the vertices of $G$ by $\{1,2,\dots ,n\}$.
• Consider all paths from $i$ to $j$ whose intermediate vertices are all drawn from $\{1,2,\dots ,k\}$
• Let $p$ be the one with minimum weight from the aforementioned paths
  • If $k\notin p$, then all intermediate vertices of $p$ belong to $\{1,2,\dots ,k-1\}$
  • If $k\in p$, decompose $p$ into $i\stackrel{p_1}{⇝}k\stackrel{p_2}{⇝}j$, the intermediate vertices of the two resulting paths are also in $\{1,2,\dots ,k-1\}$

$$d_{ij}^{(k)}=\{\begin{array}{ll}{w}_{ij},& k=0\\ \min \left\{d_{ij}^{(k-1)},d_{ik}^{(k-1)}+d_{kj}^{(k-1)}\right\},& k\ge 1\end{array}$$

• The final result is given by $D^{(n)}$
• $\Theta (n^3)$