Сетевое планирование: задача о максимальном потоке и алгоритм Диница

Главная архитектурная слабость классического подхода заключалась в хаотичном поиске увеличивающего пути. Алгоритм мог гонять поток длинными зигзагами туда-обратно по остаточной сети. Ефим Диниц предложил радикально структурировать этот поиск с помощью концепции слоистых сетей (Level Graphs). На каждой глобальной итерации (называемой фазой) алгоритм Диница запускает Поиск в ширину (Breadth-First Search, BFS) от истока к стоку. Каждой вершине графа присваивается строгий номер слоя, равный кратчайшему расстоянию от истока в терминах количества ребер. Из исходной остаточной сети безжалостно удаляются все ребра, которые ведут назад, внутри одного слоя или в обход слоев. В результате формируется идеально упорядоченная, направленная слоистая сеть, в которой движение возможно только строго вперед, на один слой ближе к цели.

Вторым гениальным нововведением стала концепция блокирующего потока (Blocking Flow). В отличие от максимального потока, блокирующий поток не обязательно является глобальным оптимумом; это просто такой поток, при котором абсолютно любой путь от истока к стоку в данной слоистой сети содержит хотя бы одно полностью насыщенное (узкое) ребро. Иными словами, поток блокирует саму возможность проложить новый путь строго вперед. Алгоритм Диница жадно и стремительно ищет эти увеличивающие пути внутри слоистой сети с помощью поиска в глубину (Depth-First Search, DFS), пока слоистая сеть не окажется полностью заблокированной.

Как только слоистая сеть блокируется, текущая фаза алгоритма завершается. Поток добавляется к общему знаменателю, строится абсолютно новая остаточная сеть, и алгоритм снова запускает BFS для формирования новой слоистой сети. Математика алгоритма Диница содержит поразительную теорему: с каждой новой фазой кратчайшее расстояние от истока к стоку (длина слоистой сети) строго и неуклонно возрастает как минимум на единицу! Поскольку максимальная длина пути без циклов в графе не может превышать общего количества вершин (V), алгоритм Диница физически не может выполнить более V фаз. Это жесткое топологическое ограничение полностью уничтожает риск бесконечного зацикливания.

Вычислительная сложность алгоритма Диница составляет O(V^2 * E), где V — число вершин, а E — число ребер. В отличие от метода Форда-Фалкерсона, эта сложность абсолютно не зависит от величины пропускных способностей труб! Даже если пропускные способности исчисляются миллиардами кубометров или являются иррациональными числами, алгоритм Диница завершит работу за строго ограниченное время. Для двудольных графов (при решении задачи о максимальном паросочетании) алгоритм работает еще быстрее, достигая феноменальной сложности O(E * sqrt(V)). Эта математическая архитектура стала предтечей современных алгоритмов проталкивания предпотока (Push-Relabel) и до сих пор широко используется инженерами при проектировании систем водоснабжения мегаполисов и оценке максимальной пропускной способности глобальных цепей поставок в условиях кризисных нагрузок.