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

'Алгоритм Дініца' - поліноміальний алгоритм для знаходження максимального потоку в транспортної мережі, запропонований в 1970 році ізраїльським (колишнім радянським) вченим Юхимом Дініцем. Тимчасова складність алгоритму становить <math> O (V ^ 2 E) </ math>. Отримати таку оцінку дозволяє введення понять допоміжної мережі і блокуючого (псевдомаксімального) потоку . У мережах з одиничними пропускними здатностями існує більш сильна оцінка часової складності: <math> O (EV) </ math>.

Опис

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

'Залишкова пропускна здатність' - відображення <math> c_f \ colon V \ times V \ to R ^ + </ math> певний як:

# Якщо <math> (u, v) \ in E </ math>,

#: <Math> c_f (u, v) = c (u, v) - f (u, v) </ math>

#: <Math> c_f (v, u) = f (u, v) </ math>

# <Math> c_f (u, v) = 0 </ math> інакше.

'Залишкова сеть' - граф <math> G_f = ((V, E_f), c_f | _ {E_f}, s, t) </ math>, де

<math> E_f = \ {(u, v) \ in V \ times V \ mid c_f (u, v)> 0 \} </ math>.

'Доповнює шлях' - <math> s-t </ math> шлях в залишковому графі <math> G_f </ math>.

Нехай <math> \ operatorname {dist} (v) </ math> - довжина найкоротшого шляху з <math> s </ math> в <math> v </ math> в графі <math> G_f </ math>. Тоді 'допоміжна сеть' графа <math> G_f </ math> - граф <math> G_L = (V, E_L, c_f | _ {E_L}, s, t) </ math>, де

<math> E_L = \ {(u, v) \ in E_f \ mid \ operatorname {dist} (v) = \ operatorname {dist} (u) + 1 \} </ math>.

'Блокуючий потік' - <math> st </ math> потік <math> f </ math> такий, що граф <math> G '= (V, E_L', s, t) </ math > з <math> E_L '= \ {(u, v) \ mid f (u, v) <c_f | _ {E_L} (u, v) \} </ math> не містить <math> st </ math > шляху.

Алгоритм

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

Вхід : Мережа <math> G = ((V, E), c, s, t) </ math>.

Вихід : <math> s-t </ math> потік <math> f </ math> максимальної величини.

1. Встановити <math> f (e) = 0 </ math> для кожного <math> e \ in E </ math>.
2. Створити <math> G_L </ math> з <math> G_f </ math> графа <math> G </ math>. Якщо <math> \ operatorname {dist} (t) = \ infty </ math>, зупинитися і вивести <math> f </ math>.
3. Знайти блокуючий потік <math> f \; '</ math> в <math> G_L </ math>.
4. Доповнити потік <math> \ f </ math> потоком <math> f \; '</ math> і перейти до кроку 2.

Аналіз

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

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

Приклад

Нижче приведена симуляція алгоритму Дініца. У допоміжній мережі <math> G_L </ math> вершини з червоними мітками - значення <math> \ operatorname {dist} (v) </ math>. Блокуючий потік позначений синім.

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

Історія

Алгоритм Дініца був опублікований в 1970 р колишнім радянським ученим Юхимом Дініцем, який зараз є членом факультету обчислювальної техніки університету Бен-Гуріон (Ізраїль), раніше, ніж алгоритм Едмондс - Карпа, який був опублікований в 1972, але створений раніше . Вони незалежно показали, що в алгоритмі Форда - Фалкерсона в разі, якщо доповнює шлях є найкоротшим, довжина доповнює шляху не зменшується.

Література

• Yefim Dinitz (2006). Dinitz 'Algorithm: The Original Version and Even's Version. У Oded Goldreich, Arnold L. Rosenberg, and Alan L. Selman (ред.). Theoretical Computer Science: Essays in Memory of [[Shimon Even]] (PDF). Springer. с. 218—240. ISBN 978-3540328803. {{cite book}}: Назва URL містить вбудоване вікіпосилання (довідка)
• B. H. Korte, Jens Vygen (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 ++