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

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

Опис

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

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

  • ,
  • ,

інакше .

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

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

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

.

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

Алгоритм

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

Аналіз

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

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

Приклад

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

Крок
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.

Посилання

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.