# 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 \overset{p_1}\leadsto k \overset{p_2}\leadsto j$, the intermediate vertices of the two resulting paths are also in $\{1, 2, \dots, k - 1\}$ $ d_{ij}^{(k)} = \begin{cases} w_{ij}, & k = 0 \\ \min\left\{ d^{(k-1)}_{ij},\; d^{(k-1)}_{ik} + d^{(k-1)}_{kj} \right\}, & k \ge 1 \end{cases} $ - The final result is given by $D^{(n)}$ - $\Theta(n^3)$