Участник:Anastasy/Алгоритм Диница: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
Строка 11: Строка 11:
 
Введём необходимые определения.  
 
Введём необходимые определения.  
  
'''Остаточной сетью''' <math>G^R</math> по отношению к сети <math>G</math> и некоторому потоку <math>f</math> в ней называется сеть, в которой каждому ребру <math>(u,v) \in G</math> с пропускной способностью <math>c_{uv}</math> и потоком <math>f_{uv}</math>  соответствуют два ребра:
+
'''Остаточной сетью''' <math>G^R</math> по отношению к сети <math>G=(V, E)</math> и некоторому потоку <math>f</math> в ней называется сеть, в которой каждому ребру <math>(u,v) \in E</math> с пропускной способностью <math>c_{uv}</math> и потоком <math>f_{uv}</math>  соответствуют два ребра:
  
 
* <math>(u,v)</math> с пропускной способностью <math>c_{uv}^R = c_{uv} - f_{uv}</math>
 
* <math>(u,v)</math> с пропускной способностью <math>c_{uv}^R = c_{uv} - f_{uv}</math>
Строка 17: Строка 17:
 
Стоит отметить, что при таком определении в остаточной сети могут появляться кратные рёбра: если в исходной сети было как ребро <math>(u,v)</math>, так и <math>(v,u)</math>.
 
Стоит отметить, что при таком определении в остаточной сети могут появляться кратные рёбра: если в исходной сети было как ребро <math>(u,v)</math>, так и <math>(v,u)</math>.
  
'''Блокирующим потоком''' в данной сети называется такой поток, что любой путь из истока <math>s</math> в сток <math>t</math> содержит насыщенное этим потоком ребро. Иными словами, в данной сети не найдётся такого пути из истока в сток, вдоль которого можно беспрепятственно увеличить поток.
+
'''Блокирующим потоком''' в данной сети называется такой поток, что любой путь из истока <math>s</math> в сток <math>t</math> содержит насыщенное этим потоком ребро (то есть <math>c_{uv} = f_{uv}</math> для некоторых <math>u,v \in V</math>. Иными словами, в данной сети не найдётся такого пути из истока в сток, вдоль которого можно беспрепятственно увеличить поток.
  
 
Блокирующий поток не обязательно максимален. Согласно теореме Форда-Фалкерсона поток будет максимальным тогда и только тогда, когда в остаточной сети <math>G^R</math> не найдётся <math>s-t</math> пути; в блокирующем же потоке ничего не утверждается о существовании пути по рёбрам, появляющимся в остаточной сети.
 
Блокирующий поток не обязательно максимален. Согласно теореме Форда-Фалкерсона поток будет максимальным тогда и только тогда, когда в остаточной сети <math>G^R</math> не найдётся <math>s-t</math> пути; в блокирующем же потоке ничего не утверждается о существовании пути по рёбрам, появляющимся в остаточной сети.

Версия 18:12, 19 октября 2017

1 Постановка задачи

1.1 Общее описание алгоритма

Алгоритм Диница [1] — полиномиальный алгоритм, предназначенный для поиска максимального потока в транспортной сети. Он был предложен советским учёным Ефимом Диницем в 1970 году. Временная сложность алгоритма [math]O(nm^2)[/math], где [math]m[/math] — число ребер, а [math]n[/math] — число вершин.

Основная идея алгоритма состоит в том, чтобы итеративно увеличивать величину потока вдоль некоторых путей из истока в сток. Алгоритм Диница схож с алгоритмом Эдмондса-Карпа[2], но основное отличие можно понимать так: на каждой итерации поток увеличивается не вдоль одного кратчайшего пути из истока в сток, а вдоль целого набора таких путей.

1.2 Математическое описание алгоритма

Математическая постановка задачи приведена в статье "Поиск максимального потока в транспортной сети", мы будем использовать введённые в ней обозначения.

Введём необходимые определения.

Остаточной сетью [math]G^R[/math] по отношению к сети [math]G=(V, E)[/math] и некоторому потоку [math]f[/math] в ней называется сеть, в которой каждому ребру [math](u,v) \in E[/math] с пропускной способностью [math]c_{uv}[/math] и потоком [math]f_{uv}[/math] соответствуют два ребра:

  • [math](u,v)[/math] с пропускной способностью [math]c_{uv}^R = c_{uv} - f_{uv}[/math]
  • [math](v,u)[/math] с пропускной способностью [math]c_{vu}^R = f_{uv}[/math]

Стоит отметить, что при таком определении в остаточной сети могут появляться кратные рёбра: если в исходной сети было как ребро [math](u,v)[/math], так и [math](v,u)[/math].

Блокирующим потоком в данной сети называется такой поток, что любой путь из истока [math]s[/math] в сток [math]t[/math] содержит насыщенное этим потоком ребро (то есть [math]c_{uv} = f_{uv}[/math] для некоторых [math]u,v \in V[/math]. Иными словами, в данной сети не найдётся такого пути из истока в сток, вдоль которого можно беспрепятственно увеличить поток.

Блокирующий поток не обязательно максимален. Согласно теореме Форда-Фалкерсона поток будет максимальным тогда и только тогда, когда в остаточной сети [math]G^R[/math] не найдётся [math]s-t[/math] пути; в блокирующем же потоке ничего не утверждается о существовании пути по рёбрам, появляющимся в остаточной сети.

Слоистая сеть для данной сети строится следующим образом. Сначала определяются длины кратчайших путей из истока s до всех остальных вершин; назовём уровнем [math]{\rm level}[v][/math] вершины её расстояние от истока. Тогда в слоистую сеть включают все те рёбра [math](u,v)[/math] исходной сети, которые ведут с одного уровня на какой-либо другой, более поздний, уровень, т.е. [math]{\rm level}[u] + 1 = {\rm level}[v][/math] (разница расстояний не может превосходить единицы, это следует из свойства кратчайших расстояний). Таким образом, удаляются все рёбра, расположенные целиком внутри уровней, а также рёбра, ведущие назад, к предыдущим уровням.

Слоистая сеть ациклична. Кроме того, любой [math]s-t[/math] путь в слоистой сети является кратчайшим путём в исходной сети.

Алгоритм представляет собой несколько фаз. На каждой фазе сначала строится остаточная сеть, затем по отношению к ней строится слоистая сеть (обходом в ширину), а в ней ищется произвольный блокирующий поток. Найденный блокирующий поток прибавляется к текущему потоку, и на этом очередная итерация заканчивается. Алгоритм заканчивает свою работу, когда в построенной на некоторой итерации остаточной сети не найдётся [math]s-t[/math] пути.

2 Программная реализация алгоритма

3 Литература

  1. Yefim Dinitz (1970). "Algorithm for solution of a problem of maximum flow in a network with power estimation". Doklady Akademii nauk SSSR.
  2. Edmonds, Jack; Karp, Richard M. (1972). "Theoretical improvements in algorithmic efficiency for network flow problems". Journal of the ACM. Association for Computing Machinery