148
правок
Изменения
Нет описания правки
Поскольку длина кратчайшего <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(VE\log V)</tex>, если использовать динамические деревья Слетора и Тарьяна.
==Реализация==
makeGl()
<tex>dist \leftarrow </tex>0
bfs()
if (<tex>t</tex> достижима)
return true
return false
algorithmDinica()
<tex>flow \leftarrow</tex> 0
while makeGL()
<tex> f' \leftarrow</tex>findBlockingFlow()
<tex> f \leftarrow f' </tex>
вывести поток <tex> f </tex>
== Источники ==
*[http://www.e-maxx.ru/algo/dinic Алгоритм Диница на e-maxx.ru]
*[http://ru.wikipedia.org/wiki/Алгоритм_Диница Алгоритм Диница на ru.wikipedia.org]
