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

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

Определение:
Слоистая сеть —это сеть состоящая только из таких рёбер $(v, u)$ сети $G$, что $d(v) + 1 = d(u)$, где $d$ - расстояние от истока.

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

1. Посторить слоистую сеть по остаточной, если сток не достижим то завершить алгоритм
2. Пустить блокирующий поток в слоистой сети

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

Утверждение:
После каждой итерации алгоритма расстояние до стока строго увеличивается

Доказательство данного факта тривиально

Так как расстояние строго увеличивается количество итераций алгоритма = $O(V)$. В зависимости от выбора алгоритма поиска блокирующего потока время данного алгоритма может составить $O(VE^2)$, $O(V^2E)$ или $O(V^3)$.

---

Автор конспекта: Станислав Донской

По всем вопросам пишите в telegram @stasana