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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Добавил уточнение, что слоистую сеть также называют вспомогательной.)
(Определение слоистой сети)
Строка 2: Строка 2:
 
Для начала определим для каждой вершины <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>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>s \leadsto t</tex> путь в слоистой сети является кратчайшим путём в исходной, из свойств обхода в ширину.
Слоистую сеть для графа G будем называть '''вспомогательной сетью'''.
 
 
[[Файл:Слоистая_сеть.png|500px |thumb|center| Слоистая сеть с пятью слоями. s = 0, t = 6]]
 
[[Файл:Слоистая_сеть.png|500px |thumb|center| Слоистая сеть с пятью слоями. s = 0, t = 6]]
 
<br/>В примере ребра, обозначенные пунктиром, не входят в слоистую сеть.
 
<br/>В примере ребра, обозначенные пунктиром, не входят в слоистую сеть.
 +
<br/><br/>Слоистую сеть для графа G будем называть '''вспомогательной сетью'''.
  
 
== Алгоритм ==
 
== Алгоритм ==

Версия 23:03, 26 ноября 2013

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

Для начала определим для каждой вершины [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] путь в слоистой сети является кратчайшим путём в исходной, из свойств обхода в ширину.

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


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

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

Алгоритм

Пусть дана сеть. Требуется найти в этой сети поток [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], если использовать динамические деревья Слетора и Тарьяна.

Реализация

  bfs()
     [math]Q \leftarrow \emptyset[/math]
     [math]Q[/math].push([math]s[/math])
     while [math]Q \ne \emptyset[/math]
        [math]u \leftarrow Q[/math].pop
        [math]for (v :[/math] поток из [math]u[/math] в [math]v[/math] положителен и [math]v[/math] не посещена)
           [math]dist[v] \leftarrow dist[u] + 1 [/math]
           [math]Q[/math].push([math]v[/math])
     [math]Q[/math].pop()
  makeGl()
     [math]dist \leftarrow 0[/math]
     bfs()
  algorithmDinica()
     [math]flow \leftarrow 0[/math]
     makeGl()
     while ([math]t[/math] достижима)
        Ищем блокирующий поток
        Меняем поток [math]f[/math]
        makeGl()
     вывести поток [math]f[/math]

Источники