Участник:Anastasy/Алгоритм Диница

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

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

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

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

Идея алгоритма состоит в следующем. Сначала величине потока присваивается 0: [math]\displaystyle{ f(u, v)=0 }[/math] для любых [math]\displaystyle{ u, v \in V }[/math].

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

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

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

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

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

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

Остаточное ребро можно понимать, как меру того, насколько можно увеличить поток вдоль некоторого ребра. Если по ребру [math]\displaystyle{ (u, v) }[/math] с пропускной способностью [math]\displaystyle{ c_{uv} }[/math] протекает поток [math]\displaystyle{ f_{uv} }[/math], то поток можно увеличить на [math]\displaystyle{ c_{uv}-f_{uv} }[/math] единиц.

Блокирующим потоком в данной сети называется такой поток, что любой путь из истока [math]\displaystyle{ s }[/math] в сток [math]\displaystyle{ t }[/math] содержит насыщенное этим потоком ребро. Иными словами, в данной сети не найдётся такого пути из истока в сток, вдоль которого можно беспрепятственно увеличить поток.

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

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

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

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