Схема алгоритма Диница — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Используемые определения)
м (rollbackEdits.php mass rollback)
 
(не показано 38 промежуточных версий 11 участников)
Строка 1: Строка 1:
== Постановка задачи ==
+
== Определение слоистой сети ==  
Пусть дана сеть, т.е. ориентированный граф <tex>G</tex>, в котором каждому ребру <tex>(u,v)</tex> приписана пропускная способность <tex>c(u,v)</tex>, а также выделены две вершины — исток <tex>s</tex> и сток <tex>t</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>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> путь во вспомогательной сети является кратчайшим путём в исходной.
+
В примере рёбра, обозначенные пунктиром, не входят в слоистую сеть.
 +
 
 +
Слоистую сеть для графа <tex>G</tex> будем называть '''вспомогательной сетью'''.
  
 
== Алгоритм ==
 
== Алгоритм ==
 +
Пусть дана [[Определение сети, потока | сеть]]. Требуется найти в этой сети [[Определение сети, потока |поток]] <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>(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>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>G_L</tex>.
#Дополним поток <tex>f</tex> найденным потоком <tex>f'</tex> и перейдем к шагу 2.
+
#Дополним поток <tex>f</tex> найденным потоком <tex>f'</tex> и перейдём к шагу 2.
  
 
=== Корректность алгоритма ===
 
=== Корректность алгоритма ===
 
Покажем, что если алгоритм завершается, то на выходе у него получается поток именно максимальной величины.
 
Покажем, что если алгоритм завершается, то на выходе у него получается поток именно максимальной величины.
  
В самом деле, предположим, что в какой-то момент во вспомогательной сети, построенной для остаточной сети, не удалось найти блокирующий поток. Это означает, что сток  вообще не достижим во вспомогательной сети из истока . Но поскольку она содержит в себе все кратчайшие пути из истока в остаточной сети, это в свою очередь означает, что в остаточной сети нет пути из истока в сток. Следовательно, применяя [[Теорема Форда-Фалкерсона|теорему Форда-Фалкерсона]], получаем, что текущий поток в самом деле максимален.
+
В самом деле, предположим, что в какой-то момент во вспомогательной сети, построенной для остаточной сети, не удалось найти блокирующий поток. Это означает, что сток  вообще не достижим во вспомогательной сети из истока. Но поскольку она содержит в себе все кратчайшие пути из истока в остаточной сети, это в свою очередь означает, что в остаточной сети нет пути из истока в сток. Следовательно, применяя [[Теорема Форда-Фалкерсона|теорему Форда-Фалкерсона]], получаем, что текущий поток в самом деле максимален.
  
=== Ассимптотика алгоритма ===
+
=== Асимптотика алгоритма ===
{{Утверждение
+
{{Теорема
 
|statement=
 
|statement=
Расстояние между истоком и стоком строго увеличивается после каждой фазы алгоритма, т.е <tex>d'[t] > d[t]</tex>, где <tex>d'[t]</tex> - значение, полученное на следующей фазе алгоритма.
+
Расстояние между истоком и стоком строго увеличивается после каждой фазы алгоритма, т.е. <tex>d'[t] > d[t]</tex>, где <tex>d'[t]</tex> значение, полученное на следующей фазе алгоритма.
 
|proof=
 
|proof=
От противного. Рассмотрим кратчайший путь из истока в сток; по предположению, его длина должна сохраниться неизменной. Однако остаточная сеть на следующей фазе содержит только рёбра остаточной сети перед выполнением текущей фазы, либо обратные к ним. Таким образом, пришли к противоречию: нашёлся <tex>s \leadsto t</tex> путь, который не содержит насыщенных рёбер, и имеет ту же длину, что и кратчайший путь. Этот путь должен был быть "заблокирован" блокирующим потоком, чего не произошло, в чём и заключается противоречие, что и требовалось доказать.
+
Проведём доказательство от противного. Пусть длина кратчайшего пути из истока в сток останется неизменной после очередной фазы алгоритма. Вспомогательная сеть строится по остаточной. Из предположения следует, что в остаточной сети будут содержаться только рёбра остаточной сети перед выполнением данной фазы, либо обратные к ним. Из этого получаем, что нашёлся <tex>s \leadsto t</tex> путь, который не содержит насыщенных рёбер и имеет ту же длину, что и кратчайший путь. Но этот путь должен был быть «заблокирован» блокирующим потоком, чего не произошло. Получили противоречие. Значит длина изменилась.
 
}}
 
}}
 
Поскольку длина кратчайшего <tex>s \leadsto t</tex> пути не может превосходить <tex>n - 1</tex>, то, следовательно, алгоритм Диница совершает не более <tex>n - 1</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>, если использовать динамические деревья Слетора и Тарьяна.
+
Таким образом, в зависимости от того, каким алгоритмом нахождения блокирующего потока мы пользовались, весь алгоритм Диница может выполняться за <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>
 +
 
 +
<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://www.e-maxx.ru/algo/dinic Алгоритм Диница на e-maxx.ru]
+
*[http://ru.wikipedia.org/wiki/Алгоритм_Диница Википедия {{---}} Алгоритм Диница]
*[http://ru.wikipedia.org/wiki/Алгоритм_Диница Алгоритм Диница на ru.wikipedia.org]
+
*[http://www.e-maxx.ru/algo/dinic MAXimal::algo::Алгоритм Диница]
 +
*Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — С. 1296. — ISBN 5-8489-0857-4
 +
 
 +
[[Категория: Алгоритмы и структуры данных]]
 +
[[Категория: Задача о максимальном потоке ]]

Текущая версия на 19:15, 4 сентября 2022

Определение слоистой сети

Для начала определим для каждой вершины [math]v[/math] данной сети [math]G[/math] длину кратчайшего [math]s \leadsto v[/math] пути из истока и обозначим её [math]d[v][/math] (для этого можно воспользоваться обходом в ширину).

В слоистую сеть включаем только те рёбра [math](u,v)[/math] исходной сети, для которых [math]d[u] + 1 = d[v][/math]. Полученная сеть ациклична, и любой [math]s \leadsto t[/math] путь в слоистой сети является кратчайшим путём в исходной, из свойств обхода в ширину.

Слоистая сеть с пятью слоями. [math]s = 0, t = 6[/math]


В примере рёбра, обозначенные пунктиром, не входят в слоистую сеть.

Слоистую сеть для графа [math]G[/math] будем называть вспомогательной сетью.

Алгоритм

Пусть дана сеть. Требуется найти в этой сети поток [math]f(u,v)[/math] из [math]s[/math] в [math]t[/math] максимальной величины.

Схема алгоритма

  1. Для каждого ребра [math](u,v)[/math] данной сети [math]G[/math] зададим [math]f(u,v) = 0[/math].
  2. Построим вспомогательную сеть [math]G_L[/math] из дополняющей сети [math]G_f[/math] данного графа [math]G[/math]. Если [math]d[t] = \infty[/math], остановиться и вывести [math]f[/math].
  3. Найдём блокирующий поток [math]f'[/math] в [math]G_L[/math].
  4. Дополним поток [math]f[/math] найденным потоком [math]f'[/math] и перейдём к шагу 2.

Корректность алгоритма

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

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

Асимптотика алгоритма

Теорема:
Расстояние между истоком и стоком строго увеличивается после каждой фазы алгоритма, т.е. [math]d'[t] \gt d[t][/math], где [math]d'[t][/math] — значение, полученное на следующей фазе алгоритма.
Доказательство:
[math]\triangleright[/math]
Проведём доказательство от противного. Пусть длина кратчайшего пути из истока в сток останется неизменной после очередной фазы алгоритма. Вспомогательная сеть строится по остаточной. Из предположения следует, что в остаточной сети будут содержаться только рёбра остаточной сети перед выполнением данной фазы, либо обратные к ним. Из этого получаем, что нашёлся [math]s \leadsto t[/math] путь, который не содержит насыщенных рёбер и имеет ту же длину, что и кратчайший путь. Но этот путь должен был быть «заблокирован» блокирующим потоком, чего не произошло. Получили противоречие. Значит длина изменилась.
[math]\triangleleft[/math]

Поскольку длина кратчайшего [math]s \leadsto t[/math] пути не может превосходить [math]n - 1[/math], то, следовательно, алгоритм Диница совершает не более [math]n - 1[/math] фазы. Таким образом, в зависимости от того, каким алгоритмом нахождения блокирующего потока мы пользовались, весь алгоритм Диница может выполняться за [math]O(VE^2)[/math] или за [math]O(V^2E)[/math]. Также возможно достичь асимптотики [math]O(VE\log V)[/math], если использовать динамические деревья Слетора и Тарьяна.

Реализация

В данной реализации не строится вспомогательная сеть [math]G_L[/math], а вычисляются значения [math]d[u][/math] — кратчайших путей [math]s \leadsto u[/math].

[math]c[u][v][/math] — пропускная способность ребра [math](uv)[/math].

[math]f[u][v][/math] — поток через ребро [math](uv)[/math].

[math]p[u][/math] номер первого неудалённого ребра, идущего из u

bool bfs():
  заполняем массив d значениями, равными [math]\infty[/math]
  d[s] = 0
  Q.push(s)
  while !Q.isEmpty
    u = Q.pop()
    for [math](uv) \in E(G)[/math]
      if f[u][v] < c[u][v] and d[v] == [math]\infty[/math]
        d[v] = d[u] + 1
        Q.push(v)
  return d[t] != [math]\infty[/math]
// поиск блокирующего потока
// u — номер вершины
// minC — минимальная пропускная способность дополняющей сети на пройденном dfs пути
int dfs(u, minC):
  if u == t or minC == 0
    return minC
  for v = p[u] to [math]|V(G)| - 1[/math]
    if d[v] == d[u] + 1 // это условие эквивалентно поиску во вспомогательной слоистой сети
      delta = dfs(v, min(minC, c[u][v] - f[u][v]))
      if delta != 0
        f[u][v] += delta // насыщаем рёбра по пути dfs
        f[v][u] -= delta
        return delta
    p[u]++
  return 0
int findMaxFlow():
  maxFlow = 0
  while bfs() // пересчитываем d[i], заодно проверяем достижима ли t из s
    заполняем p нулями
    flow = dfs(s, [math]\infty[/math])
    while flow != 0
      maxFlow += flow
      flow = dfs(s, [math]\infty[/math])
  return maxFlow

Источники