Изменения

for v in {1..n}:

<tex dpi = "105" > d^{(i)}_{uv} = min(d^{(i - 1)}_{uv}, d^{(i - 1)}_{ui} + d^{(i - 1)}_{iv}) </tex>

В итоге получаем, что матрица <tex> d^{(n)} </tex> и является искомой матрицей кратчайших путей, поскольку содержит в себе длины кратчайших путей между всеми парами вершин, имеющих в качестве промежуточных вершин вершины из множества <tex> \{ 1..n \} </tex>, что есть попросту все вершины графа. Такая реализация работает за <tex> \Theta(n^3) </tex> времени и использует <tex> \Theta(n^3) </tex> памяти.