Изменения
Восстановление правильного кода
'''if''' d[u][i] + d[i][v] < d[u][v]
d[u][v] = d[u][i] + d[i][v]
next[u][v] = next[u][i]
'''func''' getShortestPath(u, v)''':'''
</wikitex>
=== Оптимизация с помощью битовых масок ===
Строки матрицы <tex>W</tex> можно хранить с помощью массива битовых маск масок длиной <tex>k</tex>. Тогда последний цикл будет выполняться в <tex>k</tex> раз быстрее и сложность алгоритма снижается до <tex>O\Big(\fracdfrac{n^3}{k}\Big)</tex>. <br>
Пример реализации оптимизации с помощью битмасок:
W[i][j] = W[i][j] '''or''' W[k][j]
В данной реализации длина битовой маски <tex>k</tex> равна <tex>32 </tex> битам. Последний цикл делает в <tex>32 </tex> раза меньше операций {{---}} сложность алгоритма <tex>O\Big(\fracdfrac{n^3}{32}\Big)</tex>.
== Источники информации ==
