Алгоритм Диница разбирает сеть слоями и собирает максимальный поток 32 единицы на графе из четырнадцати вершин за три прохода. В 1970 году советский информатик Ефим Диниц дополнил метод Форда–Фалкерсона поиском в ширину: внутри слоя кратчайшие пути равны по числу рёбер, поэтому циклы не мешают. Основатель «Школы траблшутеров» Олег Брагинский и ученик Владислав Иванов показывают поуровневый счёт пропускной способности.
Что добавил Диниц?
Ефим Диниц дополнил алгоритм Форда–Фалкерсона двумя идеями: поиском в ширину (breadth-first search) и слоями графа. Слои избавляют от циклов, держат пути равными по числу рёбер и фиксируют блокирующие потоки.
Блокирующий поток – течение, которое полностью заполняет одно из рёбер кратчайшего пути между истоком и стоком. Насытив ребро, алгоритм закрывает направление и ищет следующее.
Слой – набор кратчайших путей, равных по числу рёбер от истока. Пути длиннее ждут следующей итерации и внутри текущего слоя не работают.
Как устроен расчёт?
- Обнулить поток и разметить вершины по уровням: уровень равен длине кратчайшего пути от истока в рёбрах, у самого истока он нулевой.
- Оставить только рёбра, ведущие с уровня на следующий, – внутри одного уровня и назад переходы запрещены правилами метода.
- Найти в слоистой сети кратчайший путь до стока и пустить по нему поток до упора.
- Повторять, пока в слое остаются маршруты: каждый насыщает хотя бы одно ребро и закрывает его до конца разбора.
- Маршруты кончились – строить новый слой; слоёв не осталось – поток максимален.
Чем Диница отличается от предшественника?
Форд–Фалкерсон берёт любой путь с запасом, поэтому число шагов зависит от величин на рёбрах. Диница раскладывает граф по уровням и выжимает кратчайшие маршруты разом.
Слой живёт, пока в нём есть непройденные маршруты. Как только каждый упирается в насыщенное ребро, строится следующий слой, и расстояние до стока растёт хотя бы на ребро.
Диница не требует сложных структур данных и просит мало памяти, а поиск в ширину делает выбор путей предсказуемым. Метод стал стандартом для задач на максимальный поток и минимальный разрез графа любой плотности.
Расплата – сложность реализации: кода больше, чем у соседей по семейству, а рекурсия упирается в глубину стека на длинных путях.
Как считает алгоритм?
Работа начинается с двух вершин: истока и стока. От истока алгоритм разбирает соседей по слоям, пока не соберёт кратчайший путь до стока, и сразу пускает по нему поток.
Пример – граф из четырнадцати вершин: рёбра направлены, веса проставлены (рисунок 1). Задача – провести поток из вершины 1 в вершину 13.
Рис. 1. Начальный граф, точка старта вершина 1
Веса на рёбрах – пропускная способность канала, а не расстояние. Алгоритм ищет не короткую дорогу, а широкую: побеждает маршрут, по которому пройдёт больше единиц за один проход.
Поиск в ширину находит кратчайшие пути до стока за три хода: 1–4–10 и 1–5–12 (рисунок 2). Бутылочные горлышки маршрутов – 4 и 9 единиц.
Рис. 2. Кратчайшие пути до стока 1–4–10 и 1–5–12 на первом слое
Кратчайшие пути исчерпаны, строим новый слой. Повторный поиск даёт два пути: 1–3–9–14 и 1–3–6–8, а стартовые 14 единиц делятся на 10 и 4.
Рис. 3. Граф с указанием второй пары кратчайших путей
Ребро 11–9 простаивает по устройству метода: работают только рёбра, ведущие на следующий уровень отдаления от истока. Обе вершины стоят на уровне 2, переход запрещён.
Слой закрыт, поиск в ширину идёт заново. Остаётся единственный путь через вершины 2–11–9–8 (рисунок 4), пять ходов до стока. Канал принимает 5 единиц.
Рис. 4. Граф с единственным оставшимся путём
Путей до стока больше нет, поэтому складываем потоки: 4 + 9 + 10 + 4 + 5 = 32 единицы.
Рис. 5. Итоговая версия графа с максимальными потоками
Пять маршрутов разошлись по трём слоям: два в первом, два во втором и один в третьем. Первый слой дал 13 единиц, второй 14, а третий всего 5 – последний путь длиннее на ход и упирается в самое узкое ребро сети.
Вершина 7 в решении не участвует: ребро ведёт в неё из вершины 8, а выхода к стоку нет. Тупиковые ветви алгоритм отбрасывает на разметке уровней, не тратя на них ходов.
Почему тридцать два – предел?
Ответ проверяют минимальным разрезом: из истока выходят четыре ребра – 5, 14, 4 и 9 единиц, вместе ровно 32, и запас у всех четырёх нулевой.
Совпадение максимального потока с минимальным разрезом – теорема Форда–Фалкерсона, на которой держится всё семейство методов. Любой другой разрез окажется не меньше, поэтому улучшить результат нельзя.
Сколько это стоит?
Временная сложность зависит прежде всего от числа вершин:
T = O(|V|2·|E|),
где T – время работы, V – число вершин, E – количество рёбер.
Память расходуется линейно по размеру графа:
Q = O(V + E),
где Q – объём памяти.
Когда применять алгоритм?
Метод закрывает сетевые задачи: транспортные, водопроводные, информационные. Им распределяют работу между сотрудниками и ресурсы между цехами, ищут совпадения в рекомендательных системах, строят маршруты и потоки пассажиров, балансируют нагрузку и сегментируют изображения.
Сетевые задачи объединяет одна форма: источник, потребитель и каналы с ограниченной пропускной способностью. Максимальный поток отвечает без перебора вариантов.
В чём преимущество Диница?
На крупных графах Диница обгоняет Эдмондса–Карпа. На единичных сетях и двудольных паросочетаниях квадрат числа вершин сменяется квадратным корнем из него.
Единичная сеть – граф, где пропускная способность каждого ребра равна единице. Такие сети возникают в задачах на паросочетания, где ребро либо выбрано, либо нет, третьего не дано.
Где Диница проигрывает?
На малых графах метод избыточен: выигрыш не заметен, а кода в разы больше. Задачи, где у рёбер есть цена, решают специализированные алгоритмы минимальной стоимости.
Что запомнить?
- Диница – Форд–Фалкерсон, у которого пути ищут поиском в ширину и раскладывают по слоям равной длины в рёбрах.
- Внутри слоя кратчайшие пути равны по числу рёбер, поэтому циклы не мешают счёту.
- Блокирующий поток насыщает одно ребро пути, после чего направление закрывается.
- Рёбра внутри уровня не работают: ребро 11–9 простояло весь разбор.
- Время – O(|V|2·|E|), память – O(V + E): граф из четырнадцати вершин отдал 32 единицы за три слоя разбора.