Изменения

== Постановка задачи Определение слоистой сети ==Пусть дана сеть, т.е. ориентированный граф Для начала определим для каждой вершины <tex>G</tex>, в котором каждому ребру <tex>(u,v)</tex> приписана пропускная способность данной сети <tex>c(u,v)G</tex>, а также выделены две вершины — исток длину кратчайшего <tex>s\leadsto v</tex> пути из истока и сток обозначим её <tex>td[v]</tex>. Требуется найти (для этого можно воспользоваться [[Обход в ширину|обходом в этой сети поток <tex>f(u,vширину]])</tex> из <tex>s</tex> в <tex>t</tex> максимальной величины.

== Используемые определения == #[[Дополняющая сеть, дополняющий путь]]#[[Блокирующий поток]]#Вспомогательная(слоистая) В слоистую сеть.::Для начала определим для каждой вершины <tex>v</tex> данной сети <tex>G</tex> длину кратчайшего <tex>s \leadsto v</tex> пути и обозначим ее <tex>d[v]</tex> (для этого можно воспользоваться [[Обход в глубину, цвета вершин|обходом в глубину]]). Тогда во вспомогательную сеть включают все включаем только те ребра рёбра <tex>(u,v)</tex> исходной сети, для которых <tex>d[u] + 1 = d[v]</tex>. ::Очевидно, полученная Полученная сеть ациклична. При этом , и любой <tex>s \leadsto t</tex> путь во вспомогательной в слоистой сети является кратчайшим путём в исходной, из свойств обхода в ширину.[[Файл:Слоистая_сеть.png|500px |thumb|center| Слоистая сеть с пятью слоями. <tex>s = 0, t = 6</tex>]]  В примере рёбра, обозначенные пунктиром, не входят в слоистую сеть. Слоистую сеть для графа <tex>G</tex> будем называть '''вспомогательной сетью'''.

#Построим вспомогательную сеть <tex>G_L</tex> из [[Дополняющая сеть, дополняющий путь|дополняющей сети ]] <tex>G_f</tex> данного графа <tex>G</tex>. Если <tex>d[t] = \infty</tex>, остановиться и вывести <tex>f</tex>.#Найдем [[Алгоритм поиска блокирующего потока в ациклической сети|Найдём блокирующий поток ]] <tex>f'</tex> в <tex>G_L</tex>. См. [[Алгоритм поиска блокирующего потока в ациклической сети]].#Дополним поток <tex>f</tex> найденным потоком <tex>f'</tex> и перейдем перейдём к шагу 2.

В самом деле, предположим, что в какой-то момент во вспомогательной сети, построенной для остаточной сети, не удалось найти блокирующий поток. Это означает, что сток вообще не достижим во вспомогательной сети из истока . Но поскольку она содержит в себе все кратчайшие пути из истока в остаточной сети, это в свою очередь означает, что в остаточной сети нет пути из истока в сток. Следовательно, применяя [[Теорема Форда-Фалкерсона|теорему Форда-Фалкерсона]], получаем, что текущий поток в самом деле максимален.

=== Ассимптотика Асимптотика алгоритма ==={{УтверждениеТеорема

Расстояние между истоком и стоком строго увеличивается после каждой фазы алгоритма, т.е . <tex>d'[t] > d[t]</tex>, где <tex>d'[t]</tex> - — значение, полученное на следующей фазе алгоритма.

От Проведём доказательство от противного. Рассмотрим кратчайший путь Пусть длина кратчайшего пути из истока в сток; по предположению, его длина должна сохраниться останется неизменнойпосле очередной фазы алгоритма. Однако остаточная Вспомогательная сеть на следующей фазе содержит строится по остаточной. Из предположения следует, что в остаточной сети будут содержаться только рёбра остаточной сети перед выполнением текущей данной фазы, либо обратные к ним. Таким образомИз этого получаем, пришли к противоречию: что нашёлся <tex>s \leadsto t</tex> путь, который не содержит насыщенных рёбер, и имеет ту же длину, что и кратчайший путь. Этот Но этот путь должен был быть "заблокирован" «заблокирован» блокирующим потоком, чего не произошло, в чём и заключается . Получили противоречие, что и требовалось доказать. Значит длина изменилась.

Таким образом, в зависимости от того, каким алгоритмом нахождения блокирующего потока мы пользовались, весь алгоритм Диница может выполняться за <tex>O(VE^2)</tex> или за <tex>O(V^2E)</tex>. Также возможно достичь ассимптотики асимптотики <tex>O(VElogVVE\log V)</tex>, если использовать [[Link-Cut_Tree | динамические деревья Слетора и Тарьяна]]. ==Реализация==В данной реализации не строится вспомогательная сеть <tex>G_L</tex>, а вычисляются значения <tex>d[u]</tex> {{---}} кратчайших путей <tex>s \leadsto u</tex>. <tex>c[u][v]</tex> {{---}} пропускная способность ребра <tex>(uv)</tex>. <tex>f[u][v]</tex> {{---}} поток через ребро <tex>(uv)</tex>. <tex>p[u]</tex> {{---}} [[Алгоритм_поиска_блокирующего_потока_в_ациклической_сети#.D0.A3.D0.B4.D0.B0.D0.BB.D1.8F.D1.8E.D1.89.D0.B8.D0.B9_.D0.BE.D0.B1.D1.85.D0.BE.D0.B4 | номер первого неудалённого ребра, идущего из u]]  '''bool''' bfs(): заполняем массив d значениями, равными <tex>\infty</tex> d[s] = 0 Q.push(s) '''while''' !Q.isEmpty u = Q.pop() '''for''' <tex>(uv) \in E(G)</tex> '''if''' f[u][v] < c[u][v] '''and''' d[v] == <tex>\infty</tex> d[v] = d[u] + 1 Q.push(v) '''return''' d[t] != <tex>\infty</tex>  <font color="darkgreen">// поиск блокирующего потока // u {{---}} номер вершины // minC {{---}} минимальная пропускная способность дополняющей сети на пройденном dfs пути</font> '''int''' dfs(u, minC): '''if''' u == t '''or''' minC == 0 '''return''' minC '''for''' v = p[u] '''to''' <tex>|V(G)| - 1</tex> '''if''' d[v] == d[u] + 1 <font color="darkgreen">// это условие эквивалентно поиску во вспомогательной слоистой сети</font> delta = dfs(v, min(minC, c[u][v] - f[u][v])) '''if''' delta != 0 f[u][v] += delta <font color="darkgreen">// насыщаем рёбра по пути dfs</font> f[v][u] -= delta '''return''' delta p[u]++ '''return''' 0  '''int''' findMaxFlow(): maxFlow = 0 '''while''' bfs() <font color="darkgreen">// пересчитываем d[i], заодно проверяем достижима ли t из s</font> заполняем p нулями flow = dfs(s, <tex>\infty</tex>) '''while''' flow != 0 maxFlow += flow flow = dfs(s, <tex>\infty</tex>) '''return''' maxFlow

*[http://wwwru.e-maxxwikipedia.ruorg/algowiki/dinic Алгоритм_Диница Википедия {{---}} Алгоритм Диница на e-maxx.ru]*[http://ruwww.wikipediae-maxx.orgru/wikialgo/Алгоритм_Диница dinic MAXimal::algo::Алгоритм Диница на ru]*Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — С.wikipedia1296.org— ISBN 5-8489-0857-4 [[Категория: Алгоритмы и структуры данных]][[Категория: Задача о максимальном потоке ]]