Відкрити головне меню

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

Зміст

ОписРедагувати

Нехай   — транспортна мережа, в якій   і   — відповідно пропускна здатність і потік через ребро  .

Залишкова пропускна здатність — відображення   як: якщо  , то:

  •  ,
  •  ,

інакше  .

Залишкова мережа — граф  , де  .

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

Нехай   — довжина найкоротшого шляху з   у   у графі  . Тоді допоміжною мережею графа   є граф  , де

 .

Блокувальний потік   — потік   такий, що граф  , де   не містить шляху  .

АлгоритмРедагувати

  • Вхід: мережа  .
  • Вихід: потік   максимальної величини  .
  1. Встановити   для кожного  .
  2. Створити   з   графа  . Якщо  , то зупинитися і вивести  .
  3. Знайти блокувальний потік   у  .
  4. Доповнити потік   потоком   і перейти до другого кроку.

АналізРедагувати

Можна показати, що щоразу кількість ребер у блокувальному потоці збільшується принаймні на одне, тому в алгоритмі не більше   блокувальних потоків, де   — кількість вершин у мережі. Допоміжна мережа   може бути побудована обходом у ширину за час  , а блокувальний потік на кожному рівні графа може бути знайдений за час  . Тому час роботи алгоритму Дініца дорівнює  .

Використовуючи такі структури даних, як динамічні дерева[en], можна знаходити блокувальний потік на кожній фазі за час  , тоді час роботи алгоритму Дініца може бути покращено до  .

ПрикладРедагувати

Нижче наведено симуляцію алгоритму Дініца. У допоміжній мережі   вершини з червоними мітками — значення  . Блокувальний потік позначено синім.

Крок      
1       Блокувальний потік складається зі шляхів:
  1.   з чотирма одиницями потоку,
  2.   з шістьома одиницями потоку,
  3.   з чотирма одиницями потоку.

Отже, блокувальний потік містить 14 одиниць потоку, а величина потоку   дорівнює 14. Варто зауважити, що доповнювальний шлях має три ребра.

2       Блокувальний потік складається з одного шляху   з п'ятьма одиницями потоку. Отже, блокувальний потік містить п'ять одиниць, а величина потоку   дорівнює  . Варто зауважити, що доповнювальний шлях має чотири ребра.
3       Сток   недосяжний у мережі  . Тому алгоритм зупиняється і повертає максимальний потік величини 19. Варто зауважити, що в кожному блокувальному потоці кількість ребер у доповнювальному шляху збільшується хоча б на одне.

ЛітератураРедагувати

  • Дініц, Юхим (2006). Dinitz' Algorithm: The Original Version and Even's Version (PDF). У Ґолдреїх, Одед; Розенберг, Арнольд Л.; Селман, Алан Л. Theoretical Computer Science: Essays in Memory of Shimon Even. Springer. с. 218—240. ISBN 978-3540328803. 
  • Корте, Б. Х.; Віген, Дженс (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. 

ПосиланняРедагувати