Изменения
Нет описания правки
== Определение слоистой сети ==
[[Файл:Слоистая_сеть.png|150px 300px |thumb|cental| Слоистая сеть с пятью слоямию. s = 0, t = 6]]
Для начала определим для каждой вершины <tex>v</tex> данной сети <tex>G</tex> длину кратчайшего <tex>s \leadsto v</tex> пути из истока и обозначим ее <tex>d[v]</tex> (для этого можно воспользоваться [[Обход в ширину|обходом в ширину]]).<br/> В слоистую сеть включаем только те ребра <tex>(u,v)</tex> исходной сети, для которых <tex>d[u] + 1 = d[v]</tex>.
Полученная сеть ациклична, и любой <tex>s \leadsto t</tex> путь во вспомогательной сети является кратчайшим путём в исходной, из свойств обхода в ширину.
Таким образом, в зависимости от того, каким алгоритмом нахождения блокирующего потока мы пользовались, весь алгоритм Диница может выполняться за <tex>O(VE^2)</tex> или за <tex>O(V^2E)</tex>. Также возможно достичь асимптотики <tex>O(VE\log V)</tex>, если использовать динамические деревья Слетора и Тарьяна.
==Реализация==
<tex>bfs()</tex>
<tex>q \leftarrow empty </tex>
<tex> q.push(s) </tex>
<tex>dist[v] \leftarrow dist[u] + 1 </tex>
<tex>q.push(v)</tex>
<tex>q.pop()</tex>
<tex>makeGl()</tex>
<tex>dist \leftarrow </tex>0
<tex>bfs()</tex> if (<tex>if (t</tex> достижима<tex>)</tex> <tex>return true</tex> <tex>return false</tex>
<tex>algorithmDinica()</tex>
<tex>flow \leftarrow</tex> 0
<tex>while makeGL()</tex> <tex> f' \leftarrowfindBlockingFlow()</tex>findBlockingFlow()
<tex> f \leftarrow f' </tex>
вывести поток <tex> f </tex>
