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

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

Опис

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

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

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

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

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

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

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

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

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

Алгоритм

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

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

Аналіз

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

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

Приклад

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

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

Література

• Дініц, Юхим (2006). Dinitz' Algorithm: The Original Version and Even's Version. У Ґолдреїх, Одед; Розенберг, Арнольд Л.; Селман, Алан Л. (ред.). (PDF). Springer. с. 218—240. ISBN . Архів оригіналу (PDF) за 20 серпня 2016. Процитовано 24 листопада 2017. {{}}: Назва 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 .

Посилання

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