Схема алгоритма Диница

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

Пусть дана сеть, т.е. ориентированный граф [math]G[/math], в котором каждому ребру [math](u,v)[/math] приписана пропускная способность [math]c(u,v)[/math], а также выделены две вершины — исток [math]s[/math] и сток [math]t[/math]. Требуется найти в этой сети поток [math]f(u,v)[/math] из [math]s[/math] в [math]t[/math] максимальной величины.

Используемые определения

1. Дополняющая сеть, дополняющий путь
2. Блокирующий поток
3. Вспомогательная (слоистая) сеть.

Для начала определим для каждой вершины [math]v[/math] данной сети [math]G[/math] длину кратчайшего [math]s \leadsto v[/math] пути и обозначим ее [math]d[v][/math] (для этого можно воспользоваться обходом в ширину). Тогда во вспомогательную сеть включают все те ребра [math](u,v)[/math] исходной сети, для которых [math]d[u] + 1 = d[v][/math].

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

Алгоритм

Схема алгоритма

1. Для каждого ребра [math](u,v)[/math] данной сети [math]G[/math] зададим [math]f(u,v) = 0[/math].
2. Построим вспомогательную сеть [math]G_L[/math] из дополняющей сети [math]G_f[/math] данного графа [math]G[/math]. Если [math]d[t] = \infty[/math], остановиться и вывести [math]f[/math].
3. Найдем блокирующий поток [math]f'[/math] в [math]G_L[/math]. См. Алгоритм поиска блокирующего потока в ациклической сети.
4. Дополним поток [math]f[/math] найденным потоком [math]f'[/math] и перейдем к шагу 2.

Корректность алгоритма

Покажем, что если алгоритм завершается, то на выходе у него получается поток именно максимальной величины.

В самом деле, предположим, что в какой-то момент во вспомогательной сети, построенной для остаточной сети, не удалось найти блокирующий поток. Это означает, что сток вообще не достижим во вспомогательной сети из истока. Но поскольку она содержит в себе все кратчайшие пути из истока в остаточной сети, это в свою очередь означает, что в остаточной сети нет пути из истока в сток. Следовательно, применяя теорему Форда-Фалкерсона, получаем, что текущий поток в самом деле максимален.

Асимптотика алгоритма

Утверждение:

Расстояние между истоком и стоком строго увеличивается после каждой фазы алгоритма, т.е. [math]d'[t] \gt d[t][/math], где [math]d'[t][/math] — значение, полученное на следующей фазе алгоритма.

[math]\triangleright[/math]

От противного. Рассмотрим кратчайший путь из истока в сток; по предположению, его длина должна сохраниться неизменной. Однако остаточная сеть на следующей фазе содержит только рёбра остаточной сети перед выполнением текущей фазы, либо обратные к ним. Таким образом, пришли к противоречию: нашёлся [math]s \leadsto t[/math] путь, который не содержит насыщенных рёбер и имеет ту же длину, что и кратчайший путь. Этот путь должен был быть «заблокирован» блокирующим потоком, чего не произошло, в чём и заключается противоречие, что и требовалось доказать.

[math]\triangleleft[/math]

Поскольку длина кратчайшего [math]s \leadsto t[/math] пути не может превосходить [math]n - 1[/math], то, следовательно, алгоритм Диница совершает не более [math]n - 1[/math] фазы. Таким образом, в зависимости от того, каким алгоритмом нахождения блокирующего потока мы пользовались, весь алгоритм Диница может выполняться за [math]O(VE^2)[/math] или за [math]O(V^2E)[/math]. Также возможно достичь асимптотики [math]O(VE\log V)[/math], если использовать динамические деревья Слетора и Тарьяна.

Источники

• Алгоритм Диница на e-maxx.ru
• Алгоритм Диница на ru.wikipedia.org