Изменения
→Алгоритм Флойда
====Алгоритм Флойда====
{{main|Алгоритм Флойда}}
'''Алгоритм Флойда–Уоршелла''' (англ. ''the Floyd–Warshall algorithm'') {{---}} алгоритм, разработанный в <tex>1962</tex> году Робертом Флойдом <ref> [https://ru.wikipedia.org/wiki/Флойд,_Роберт|Роберт ФлойдРоберт_Флойд]</ref> и Стивеном Уоршеллом для нахождения длин кратчайших путей между всеми парами вершин во взвешенном ориентированном графе. Работает корректно, если в графе нет циклов отрицательной величины, а если же такой цикл есть, позволяет найти хотя бы один такой цикл. Асимптотическая сложность алгоритма <tex> \Theta(n^3) </tex>, также требует <tex> \Theta(n^2) </tex> памяти.
В модификации данного алгоритма для [[Алгоритм_Флойда#Построение_транзитивного_замыкания|построения транзитивного замыкания]] можно применить оптимизацию с помощью битовых масок. С помощью неё можно добиться улучшения времени работы. Если обозначить за <tex> k </tex> длину битовой макси, то асимптотическая сложность алгоритма поменяется и станет равна <tex>O\Big(\dfrac{n^3}{k}\Big).</tex>
