16
правок
Изменения
→Ассимптотика алгоритма
}}
Поскольку длина кратчайшего <tex>s \leadsto t</tex> пути не может превосходить <tex>n - 1</tex>, то, следовательно, алгоритм Диница совершает не более <tex>n - 1</tex> фазы.
Таким образом, в зависимости от того, каким алгоритмом нахождения блокирующего потока мы пользовались, весь алгоритм Диница может выполняться за <tex>O(VE^2)</tex> или за <tex>O(V^2E)</tex>. Также возможно достичь ассимптотики <tex>O(VElogVVE\log V)</tex>, если использовать динамические деревья Слетора и Тарьяна.
== Источники ==
*[http://www.e-maxx.ru/algo/dinic Алгоритм Диница на e-maxx.ru]
*[http://ru.wikipedia.org/wiki/Алгоритм_Диница Алгоритм Диница на ru.wikipedia.org]
