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

Алгоритм Диница

Автор: Киреева Анастасия, группа 416

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.3 Вычислительное ядро алгоритма

Наибольший объем вычислений приходится на:

• поиск в ширину (для построения слоистой сети)
• обход в глубину (для построения блокирующего потока)

1.4 Макроструктура алгоритма

Одним из важных шагов алгоритма является поиск блокирующего потока. Опишем, каким образом это можно сделать.

Ищем $s-t$ пути по одному обходом в глубину, пока такие пути находятся, при этом удаляем те ребра, вдоль которых невозможно дойти до стока. Для этого достаточно удалять ребро после того, как мы просмотрели его в обходе в глубину (кроме того случая, когда мы прошли вдоль ребра и нашли путь до стока). С точки зрения реализации, надо просто поддерживать в списке смежности каждой вершины указатель на первое неудалённое ребро, и увеличивать этот указатель в цикле внутри обхода в глубину.

1.5 Схема реализации последовательного алгоритма

Структуру алгоритма можно описать следующим образом:

1. Для всех ребер $(u, v) \in E$ сети $G$ присвоим $f_{uv}=0$.
2. Построим остаточную сеть $G^R$ по отношению к сети $G$ и потоку $f$. Затем строим слоистую сеть $G^L$ по отношению к сети $G^R$. Если ${\rm level}[t]=∞$, алгоритм завершает работу и выводит поток $f$.
3. Ищем блокирующий поток $f'$ в сети $G^R$
4. Прибавим $f'$ к потоку $f$ и переходим к шагу 2.

1.6 Последовательная сложность алгоритма

• С помощью поиска в ширину слоистая сеть строится за время $O(m)$.
• Если обход в глубину достигает стока, насыщается как минимум одно ребро, иначе как минимум один указатель продвигается вперед. Таким образом, один запуск обхода в глубину работает за $O(n + k)$, где $k$ — число продвижения указателей. Ввиду того, что всего запусков обхода в глубину в рамках поиска одного блокирующего потока будет $O(p)$, где $p$ — число рёбер, насыщенных этим блокирующим потоком, то весь алгоритм поиска блокирующего потока отработает за $O(pn + \sum\limits_i{k_i})$. Учитывая, что все указатели в сумме прошли расстояние $O(m)$, это дает асимптотику $O(pn + pk)$. В худшем случае, когда блокирующий поток насыщает все рёбра, асимптотика получается $O(mn)$.
• Можно показать, что после каждой итерации расстояние между стоком и истоком строго увеличивается (то есть ${\rm level'}[t] \gt {\rm level}[t]$, где ${\rm level'}[t]$ — расстояние до стока, полученное на следующей итерации). Так как длина кратчайшего $s-t$ пути не может превосходить $n - 1$, то и количество фаз алгоритма не превосходит $n - 1$. Таким образом, весь алгоритм Диница выполняется за $O(n^2m)$.

1.7 Информационный граф

• 

  Рисунок 1. Информационный граф алгоритма Диница
• 

  Рисунок 2. Информационный граф поиска в ширину

Для алгоритма Диница:

1. Инициализация переменных
2. Вызов функции поиска в ширину
3. (3.1 - 3.k) выполнение функции поиска в глубину, итеративно увеличивается поток
4. Вызов функции поиска в ширину. В случае существования пути до стока, переход на следующую итерацию (начиная с поиска в глубину), иначе вывод вычисленной величины потока.

Для поиска в ширину

1. Инициализация расстояния до истока ($d[s] = 0$) и текущего уровня нулю ($level = 0$).
2. Извлечение очередной вершины из множества вершин, соответствующего процессу ($v \in V_{node}$). Вершина обрабатывается, если расстояние до нее равно текущему уровню ($d[v] == level$)
3. Обход соседей вершин. В случае если вершина $u$ принадлежит $V_{node}$, значение пути до этой вершины инициализируется $d[u] = level + 1$. Иначе она помечается для дальнейшей обработки другим процессом.
4. Слияние информации по помеченным вершинам (в общем массиве помечаются все вершины, которые были помечены хотя бы один раз)
5. Для всех помеченных необработанных ($d[v] == -1$) вершин, принадлежащих $V_{node}$, расстояние принимается равным $level + 1$
6. Если было обновлено расстояние хотя бы до одной вершины, переход на следующую итерацию, иначе выход из цикла

1.8 Ресурс параллелизма алгоритма

В приведенном варианте алгоритма поиска в ширину граф обходится по слоям, то есть на каждой итерации обрабатывается множество вершин, расстояние до которых одинаково. Число слоев не превосходит $n - 1$, таким образом, высота ярусно-параллельной формы алгоритма поиска в ширину равна $O(n)$.

Так как поиск блокирующего потока производится последовательно, его высота ярусно-параллельной формы алгоритма совпадает с его последовательной сложностью $O(nm)$.

Так как число шагов алгоритма не превосходит $n$, высота ЯПФ алгоритма Диница равна $O(n^2m)$.

В описанном алгоритме поиска в ширину вершины разделяются между процессами поровну, поэтому ширина ЯПФ поиска в ширину и алгоритма Диница равна $n$.

1.9 Входные и выходные данные алгоритма

Входные данные: Граф $G(V, E)$. $n$ вершин $v_i$ и $m$ ребер $e_j = (v_j^{(1)}, v_j^{(2)})$ с заданной пропускной способностью $c_j$, а также исток $s$ и сток $t$.

Объем входных данных: $O(m + n)$.

Выходные данные: величина максимального потока.

Объем выходных данных: $O(1)$.

1.10 Свойства алгоритма

В зависимости от порядка обработки ребер графа, вычисленные блокирующие потоки на соответствующих итерациях могут быть различны, кроме того, может поменяться количество итераций алгоритма Диница.

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

2.4 Масштабируемость алгоритма и его реализации

Набор и границы значений изменяемых параметров запуска реализации алгоритма:

• число процессоров $[2^k, k = 0, 1, ...7]$;
• число вершин графа [5 000:20 000] с шагом 5000. Количество ребер одинаково для всех графов и равно 2 500 000.

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

График зависимости ускорения от количества процессов и количества вершин графа (рис. 4) более нагляден, так как количество итераций в алгоритме не зависит от количества процессов и время выполнения пропорционально числу итераций. По этому графику видно, что ускорение падает с увеличением размера графа.

• 

  Рисунок 3. График зависимости производительности от количества процессов и количества вершин графа
• 

  Рисунок 3. График зависимости производительности от количества процессов и количества вершин графа

2.7 Существующие реализации алгоритма

• Python: NetworkX (функция dinitz): алгоритм Диница