Loading AI tools
З Вікіпедії, вільної енциклопедії
Алгоритм Дініца — поліноміальний алгоритм для знаходження максимального потоку у транспортної мережі, запропонований 1970 року ізраїльським (колишнім радянським) ученим Юхимом Дініцем. І алгоритм Дініца, і алгоритм Едмондса-Карпа незалежно показують, що в алгоритмі Форда — Фалкерсона в разі найкоротшого доповнювального шляху його довжина доповнює шляху не зменшується. Часова складність алгоритму становить . Отримати таку оцінку дозволяє введення понять допоміжної мережі та блокуючого (псевдомаксимального) потоку. В мережах з одиничними пропускними здатностями існує сильніша оцінка часової складності: .
Нехай — транспортна мережа, в якій і — відповідно пропускна здатність і потік через ребро .
Залишкова пропускна здатність — відображення як: якщо , то:
інакше .
Залишкова мережа — граф , де .
Доповнювальний шлях — шлях у залишковому графі .
Нехай — довжина найкоротшого шляху з у у графі . Тоді допоміжною мережею графа є граф , де
Блокувальний потік — потік такий, що граф , де не містить шляху .
Можна показати, що щоразу кількість ребер у блокувальному потоці збільшується принаймні на одне, тому в алгоритмі не більше блокувальних потоків, де — кількість вершин у мережі. Допоміжна мережа може бути побудована обходом у ширину за час , а блокувальний потік на кожному рівні графа може бути знайдений за час . Тому час роботи алгоритму Дініца дорівнює .
Використовуючи такі структури даних, як динамічні дерева[en], можна знаходити блокувальний потік на кожній фазі за час , тоді час роботи алгоритму Дініца може бути покращено до .
Нижче наведено симуляцію алгоритму Дініца. У допоміжній мережі вершини з червоними мітками — значення . Блокувальний потік позначено синім.
{{cite book}}
: Назва URL містить вбудоване вікіпосилання (довідка)Ця стаття містить правописні, лексичні, граматичні, стилістичні або інші мовні помилки, які треба виправити. (листопад 2017) |
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.