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

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

Опис

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

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

• $c_f(u,v)=c(u,v)-f(u,v)$,
• $c_f(v,u)=f(u,v)$,

інакше $c_f(u,v)=0$.

Залишкова мережа — граф $G_f=((V,E_f),c_f{|}_{E_f},s,t)$, де $E_f=\{(u,v)\in V\times V\mid c_f(u,v)>0\}$.

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

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

$E_L=\{(u,v)\in E_f\mid \mathrm{dist}\left(v\right)=\mathrm{dist}\left(u\right)+1\}$.

Блокувальний потік $st$ — потік $f$ такий, що граф $G^{\prime }=(V,{E_L}^{\prime },s,t)$, де ${E_L}^{\prime }=\{(u,v)\mid f(u,v)<c_f{|}_{E_L}(u,v)\}$ не містить шляху $st$.

Алгоритм

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

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

Аналіз

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

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

Приклад

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

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

Література

• Шаблон:Cite book
• Шаблон:Cite book

Посилання

• Шаблон:Url