Викиконспекты - Вклад участника [ru]

Схема алгоритма Диница

2015-12-18T10:14:28Z

109.167.138.105:

== Определение слоистой сети ==
Для начала определим для каждой вершины <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| Слоистая сеть с пятью слоями. s = 0, t = 6]]
 В примере ребра, обозначенные пунктиром, не входят в слоистую сеть.
 Слоистую сеть для графа G будем называть '''вспомогательной сетью'''.

== Алгоритм ==
Пусть дана [[Определение сети, потока | сеть]]. Требуется найти в этой сети [[Определение сети, потока |поток]] <tex>f(u,v)</tex> из <tex>s</tex> в <tex>t</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.

=== Корректность алгоритма ===
Покажем, что если алгоритм завершается, то на выходе у него получается поток именно максимальной величины.

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

=== Асимптотика алгоритма ===
{{Теорема
|statement=
Расстояние между истоком и стоком строго увеличивается после каждой фазы алгоритма, т.е. <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 | динамические деревья Слетора и Тарьяна]].

==Реализация==
В данной реализации не строится вспомогательная сеть <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>

//поиск блокирующего потока
//u - номер вершины
//cf - минимальная пропускная способность дополняющей сети на пройденном dfs пути
'''int''' dfs(u, cf):
'''if''' u == t '''or''' cf == 0
'''return''' cf
'''for''' v = p[u] '''to''' <tex>|V(G)| - 1</tex>
'''if''' d[v] == d[u] + 1 //это условие эквивалентно поиску во вспомогательной слоистой сети
cfmin = dfs(v, min(cf, c[u][v] - f[u][v]))
'''if''' cfmin != 0
f[u][v] += cfmin //насыщаем ребра по пути dfs
f[v][u] -= cfmin
'''return''' cfmin
p[u]++
'''return''' 0

'''int''' findMaxFlow():
maxFlow = 0
'''while''' bfs() //пересчитываем d[i], заодно проверяем достижима ли t из s
заполняем p нулями
flow = dfs(s, <tex>\infty</tex>)
'''while''' flow != 0
maxFlow += flow
flow = dfs(s, <tex>\infty</tex>)
'''return''' maxFlow
== Источники ==
*[http://www.e-maxx.ru/algo/dinic Алгоритм Диница на e-maxx.ru]
*[http://ru.wikipedia.org/wiki/Алгоритм_Диница Алгоритм Диница на ru.wikipedia.org]
*Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — С. 1296. — ISBN 5-8489-0857-4

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о максимальном потоке ]]

Схема алгоритма Диница

2015-12-18T00:42:39Z

109.167.138.105:

== Определение слоистой сети ==
Для начала определим для каждой вершины <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| Слоистая сеть с пятью слоями. s = 0, t = 6]]
 В примере ребра, обозначенные пунктиром, не входят в слоистую сеть.
 Слоистую сеть для графа G будем называть '''вспомогательной сетью'''.

== Алгоритм ==
Пусть дана [[Определение сети, потока | сеть]]. Требуется найти в этой сети [[Определение сети, потока |поток]] <tex>f(u,v)</tex> из <tex>s</tex> в <tex>t</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.

=== Корректность алгоритма ===
Покажем, что если алгоритм завершается, то на выходе у него получается поток именно максимальной величины.

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

=== Асимптотика алгоритма ===
{{Теорема
|statement=
Расстояние между истоком и стоком строго увеличивается после каждой фазы алгоритма, т.е. <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 | динамические деревья Слетора и Тарьяна]].

==Реализация==
В данной реализации не строится вспомогательная сеть <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>.

'''bool''' bfs():
заполняем массив d значениями, равными -1
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] != -1
d[v] = d[u] + 1
Q.push(v)
'''return''' d[t] != -1

//поиск блокирующего потока
//v - номер вершины
//cf - минимальная пропускная способность дополняющей сети на пройденном dfs пути
'''int''' dfs(u, cf):
'''if''' u == t '''or''' cf == 0
'''return''' cf
//p[u] - номер вершины на которой завершился обход для вершины u
'''for''' v = p[u] '''to''' <tex>|V(G)| - 1</tex>
'''if''' d[v] == d[u] + 1 //это условие эквивалентно поиску во вспомогательной слоистой сети
cfmin = dfs(v, min(cf, c[u][v] - f[u][v]))
f[u][v] += cfmin
f[v][u] -= cfmin
'''return''' cfmin
p[u]++
'''return''' 0

'''int''' findMaxFlow():
maxFlow = 0
'''while''' bfs() //пересчитываем d[i], заодно проверяем достижима ли t из s
заполняем p нулями
flow = dfs(s, <tex>\infty</tex>)
'''while''' flow != 0
maxFlow += flow
flow = dfs(s, <tex>\infty</tex>)
'''return''' maxFlow
== Источники ==
*[http://www.e-maxx.ru/algo/dinic Алгоритм Диница на e-maxx.ru]
*[http://ru.wikipedia.org/wiki/Алгоритм_Диница Алгоритм Диница на ru.wikipedia.org]
*Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — С. 1296. — ISBN 5-8489-0857-4

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о максимальном потоке ]]