442
правки
Изменения
→Определение слоистой сети
== Определение слоистой сети ==
Для начала определим для каждой вершины <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> путь во вспомогательной в слоистой сети является кратчайшим путём в исходной, из свойств обхода в ширину.[[Файл:Слоистая_сеть.png|300px 500px |thumb|center| Слоистая сеть с пятью слоями. <tex>s = 0, t = 6</tex>]]<br/> В примере ребрарёбра, обозначенные пунктиром, не входят в слоистую сеть. Слоистую сеть для графа <tex>G</tex> будем называть '''вспомогательной сетью'''.
== Алгоритм ==
#Для каждого ребра <tex>(u,v)</tex> данной сети <tex>G</tex> зададим <tex>f(u,v) = 0</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> — значение, полученное на следующей фазе алгоритма.
|proof=
Проведём доказательство от противного. Пусть длина кратчайшего пути из истока в сток останется неизменной после очередной фазы алгоритма. Вспомогательная сеть строится по остаточной. Из предположения следует, что в остаточной сети будет будут содержаться только рёбра остаточной сети перед выполнением данной фазы, либо обратные к ним. Из этого получаем, что нашёлся <tex>s \leadsto t</tex> путь, который не содержит насыщенных рёбер и имеет ту же длину, что и кратчайший путь. Но этот путь должен был быть «заблокирован» блокирующим потоком, чего не произошло. Получили противоречие. Значит длина изменилась.
}}
Поскольку длина кратчайшего <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>, если использовать [[Link-Cut_Tree | динамические деревья Слетора и Тарьяна]].
==Реализация==
== Источники ==
*[http://wwwru.e-maxxwikipedia.ruorg/algowiki/dinic Алгоритм_Диница Википедия {{---}} Алгоритм Диница на e-maxx.ru]*[http://ruwww.wikipediae-maxx.orgru/wikialgo/Алгоритм_Диница dinic MAXimal::algo::Алгоритм Диница на ru.wikipedia.org]
*Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — С. 1296. — ISBN 5-8489-0857-4
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о максимальном потоке ]]