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

Алгоритм Дініца — поліноміальний алгоритм для знаходження максимального потоку у транспортної мережі, запропонований 1970 року ізраїльським (колишнім радянським) ученим Юхимом Дініцем. І алгоритм Дініца, і алгоритм Едмондса-Карпа незалежно показують, що в алгоритмі Форда — Фалкерсона в разі найкоротшого доповнювального шляху його довжина доповнює шляху не зменшується. Часова складність алгоритму становить $O\left(V^{2}E\right)$. Отримати таку оцінку дозволяє введення понять допоміжної мережі та блокуючого (псевдомаксимального) потоку. В мережах з одиничними пропускними здатностями існує сильніша оцінка часової складності: $O\left(EV\right)$.

Опис

Нехай $G=\left(\left(V,E\right),c,s,t\right)$ — транспортна мережа, в якій $c\left(u,v\right)$ і $f\left(u,v\right)$ — відповідно пропускна здатність і потік через ребро $\left(u,v\right)$.

Залишкова пропускна здатність — відображення $c_{f}\colon V\times V\to R^{+}$ як: якщо $\left(u,v\right)\in E$, то:

• $c_{f}\left(u,v\right)=c\left(u,v\right)-f\left(u,v\right)$,
• $c_{f}\left(v,u\right)=f\left(u,v\right)$,

інакше $c_{f}\left(u,v\right)=0$.

Залишкова мережа — граф $G_{f}=\left(\left(V,E_{f}\right),c_{f}|_{E_{f}},s,t\right)$, де $E_{f}=\lbrace \left(u,v\right)\in V\times V\mid c_{f}\left(u,v\right)>0\rbrace$.

Доповнювальний шлях $s-t$ — шлях у залишковому графі $G_{f}$.

Нехай $\operatorname {dist} \left(v\right)$ — довжина найкоротшого шляху з $s$ у $v$ у графі $G_{f}$. Тоді допоміжною мережею графа $G_{f}$ є граф $G_{L}=\left(V,E_{L},c_{f}|_{E_{L}},s,t\right)$, де

$E_{L}=\lbrace \left(u,v\right)\in E_{f}\mid \operatorname {dist} \left(v\right)=\operatorname {dist} \left(u\right)+1\rbrace$.

Блокувальний потік $st$ — потік $f$ такий, що граф $G'=\left(V,E_{L}',s,t\right)$, де $E_{L}'=\lbrace \left(u,v\right)\mid f\left(u,v\right)<c_{f}|_{E_{L}}\left(u,v\right)\rbrace$ не містить шляху $st$.

Алгоритм

• Вхід: мережа $G=\left(\left(V,E\right),c,s,t\right)$.
• Вихід: потік $s-t$ максимальної величини $f$.

1. Встановити $f\left(e\right)=0$ для кожного $e\in E$.
2. Створити $G_{L}$ з $G_{f}$ графа $G$. Якщо $\operatorname {dist} \left(t\right)=\infty$, то зупинитися і вивести $f$.
3. Знайти блокувальний потік $f'$ у $G_{L}$.
4. Доповнити потік $f$ потоком $f'$ і перейти до другого кроку.

Аналіз

Можна показати, що щоразу кількість ребер у блокувальному потоці збільшується принаймні на одне, тому в алгоритмі не більше $n-1$ блокувальних потоків, де $n$ — кількість вершин у мережі. Допоміжна мережа $G_{L}$ може бути побудована обходом у ширину за час $O\left(E\right)$, а блокувальний потік на кожному рівні графа може бути знайдений за час $O\left(VE\right)$. Тому час роботи алгоритму Дініца дорівнює $O\left(V\right)*\left(O\left(E\right)+O\left(VE\right)\right)=O\left(V^{2}E\right)$.

Використовуючи такі структури даних, як динамічні дерева, можна знаходити блокувальний потік на кожній фазі за час $O\left(E\log V\right)$, тоді час роботи алгоритму Дініца може бути покращено до $O\left(VE\log V\right)$.

Приклад

Нижче наведено симуляцію алгоритму Дініца. У допоміжній мережі $G_{L}$ вершини з червоними мітками — значення $\operatorname {dist} \left(v\right)$. Блокувальний потік позначено синім.

Крок	$G$	$G_{f}$	$G_{L}$
1				Блокувальний потік складається зі шляхів: $\lbrace s,1,3,t\rbrace$ з чотирма одиницями потоку, $\lbrace s,1,4,t\rbrace$ з шістьома одиницями потоку, $\lbrace s,2,4,t\rbrace$ з чотирма одиницями потоку. Отже, блокувальний потік містить 14 одиниць потоку, а величина потоку $\left|f\right|$ дорівнює 14. Варто зауважити, що доповнювальний шлях має три ребра.
2				Блокувальний потік складається з одного шляху $\lbrace s,2,4,3,t\rbrace$ з п'ятьма одиницями потоку. Отже, блокувальний потік містить п'ять одиниць, а величина потоку $\left|f\right|$ дорівнює $14+5=19$. Варто зауважити, що доповнювальний шлях має чотири ребра.
3				Сток $t$ недосяжний у мережі $G_{f}$. Тому алгоритм зупиняється і повертає максимальний потік величини 19. Варто зауважити, що в кожному блокувальному потоці кількість ребер у доповнювальному шляху збільшується хоча б на одне.

Література

• Дініц, Юхим (2006). Dinitz' Algorithm: The Original Version and Even's Version. У Ґолдреїх, Одед; Розенберг, Арнольд Л.; Селман, Алан Л. (ред.). Theoretical Computer Science: Essays in Memory of [[Shimon Even]] (PDF). Springer. с. 218—240. ISBN 978-3540328803. Архів оригіналу (PDF) за 20 серпня 2016. Процитовано 24 листопада 2017. {{cite book}}: Назва URL містить вбудоване вікіпосилання (довідка)
• Корте, Б. Х.; Віген, Дженс (2008). 8.4 Blocking Flows and Fujishige's Algorithm. Combinatorial Optimization: Theory and Algorithms (Algorithms and Combinatorics, 21). Springer Berlin Heidelberg. с. 174—176. ISBN 978-3-540-71844-4.

Посилання

• Алгоритм Дініца на сайті e-maxx.ru: Опис, докази, реалізація на C++