Алгоритм Дініка для максимального потоку

Чому алгоритм Едмонса-Карпа вичерхується

Алгоритм Едмонса-Карпа є стандартним рішенням для недетермінованості алгоритму Форда-Фулкерона: замість вибору будь-якого посилювального шляху, завжди використовуйте пошук у ширину (BFS) для знаходження найкоротшого посилювального шляху за кількістю ребер. Це гарантує завершення та доведений ліміт O(V * E^2), але алгоритм все ще розглядає кожен окремий посилювальний шлях як ізольоване подія. Після просування потоку вздовж одного шляху весь деревоподібний об’єкт BFS відкидається, і наступна ітерація знову шукає в графі залишків з порожнього положення, хоча структура більшості графа не змінилася взагалі. У графах із багатьма паралельними шляхами найближчими до найкоротших, це означає повторне обчислення дуже схожих пошуків у ширину знову і знову, платячи повну вартість O(E) переходу для кожного знайденого окремого шляху. Втрати праці не полягають у неправильному пошуку шляхів, а в тому, що все вивчене забувається після знаходження лише одного шляху. Інтуїція Дініка полягала в тому, що один прохід BFS вже розкриває найкоротшу відстань від джерела до кожного вузла, і ця інформація залишається дійсною для просування потоку вздовж багатьох шляхів, не лише одного, за умови, що ці шляхи поважають одне й те саме шарування. Замість одного посилювального шляху на BFS Діні використовував весь максимальний пакет посилювальних шляхів, який називається блокуючим потоком, з єдиного рівневого графа перед будь-яким запуском BFS ще раз. Блокуючий потік — це призначення потоку, таке що кожен шлях від джерела до кінцевої точки в рівневому графі має принаймні один насичений край, тобто через цей край не можна перемістити додатковий потік без перевищення його ємності. Знаходження цього блокуючого потоку все ще потребує пошуку, але це може бути виконано одним об’їздом у глибину, доповненим веденням покажчиків, замість одного об’їзду на шлях. В результаті дорогі перерахування BFS відбуваються лише O(V) разів загалом протягом всього алгоритму, а не один раз на посилювальний шлях, і ця реструктуризація відрізняє складність алгоритму Дініка від складності алгоритму Едмонса-Карпа.

Побудова графу рівнів за допомогою пошуку в ширину

На кожному етапі алгоритму Дініка запускається справжній пошук у ширину від витоку по поточній графі залишкових можливостей, графі, створеному для кожного краю, який все ще має невикористаний пропускний ресурс після врахування потоку, що вже був переміщений вздовж нього та його зворотнього краю. BFS призначає кожній досягнутій ноді номер рівня рівного мінімальній кількості залишкових ребер, необхідних для досягнення її з витоку, точно так само, як і стандартний пошук найкоротших шляхів BFS обчислює. Лише ребра, що переміщуються від рівня L до рівня L+1, зберігаються в графі рівнів; будь-який залишковий край, який з'єднує вузли на одному рівні або вказує назад на нижчий рівень, відкидається, навіть якщо він має запасний пропускний ресурс. Це обрізання є важливим і саме воно забезпечує ефективність наступного пошуку у глибину, оскільки воно гарантує, що кожен шлях, знайдений в графі рівнів, автоматично є найкоротшим шляхом у графі залишкових можливостей, і запобігає DFS безглуздім витратам часу на блукання по тупиках або циклах. Якщо BFS завершується без досягнення вузла призначення, це сигнал зупинки алгоритму: не існує жодного шляху посилення ніде в графі залишкових можливостей, граф рівнів порожній і не має значення, а поточний потік вже є максимальним потоком відповідно до теореми про максимальний потік та мінімальний розріз. Побудова графу рівнів займає O(E) часу та O(V) часу для самого переходу, оскільки BFS відвідує кожен вузол один раз і досліджує кожен край щонайбільше один раз. Варто підкреслити, що граф рівнів є спряженим циклом за конструкцією, оскільки ребра строго збільшують рівень, і ця властивість циклу точно пояснює, чому DFS фаза може безпечно використовувати однопрохідну розрахунок покажчиків без повторного відвідування повністю дослідженого тупика більше одного разу. Коли цей BFS крок запускається, гарантовано, що найкоротша відстань від витоку до призначення, виміряна по графі залишкових можливостей, збільшується порівняно з попереднім етапом, що лежить в основі доведення складності для алгоритму.

Знаходження блокуючого потоку за допомогою глибинного пошуку

З фіксованою графоподібною структурою для цієї фази, алгоритм Дініка переходить до глибинного пошуку (DFS), завдання якого – знайти блокуючий потік, максимальний набір збільшувальних шляхів через рівневу графіку, такий що через нього неможливо направити додаткову одиницю потоку. DFS починається з джерела і жадібно йде вперед вздовж ребер рівневої графіки, завжди просуваючись до наступного рівня, поки не досягне призначення, у цьому випадку відправляючи потік, рівний мінімальному завантаженню, вздовж виявленого шляху, або поки не зустріне тупик без можливості подальшого руху вперед, у такому разі відступає назад. Ключова оптимізація ефективності полягає в підтримці для кожного вузла поточного покажчика або індексу ітератора у його списку сусідніх елементів. Після того, як ребро повністю насичено, або після того, як пошук визначає, що вузол не може дістатися до призначення, DFS переміщує цей покажчик за вичерпане ребро та більше його не розглядає під час цієї фази. Це означає, що кожне ребро рівневої графіки досліджується та відкидається не більше ніж один раз на фазу, а не один раз для кожного збільшувального шляху, тому весь пошук блокуючого потоку по всіх шляхах в одній фазі коштує лише O(V * E) у найгіршому випадку, оскільки кожен з до O(V) збільшувальних шляхів, які знаходяться, може потребувати O(V) ребер для проходження, а переміщення покажчика забезпечує амортизовану вартість сканування ребер. Цей єдиний прохід DFS, відправляючи потік вздовж кількох шляхів без перезапуску, є механічним серцем переваги швидкості алгоритму Дініка. Коли DFS більше не може дістатися до призначення з джерела за допомогою незаповнених рівневих ребер, блокуючий потік для цієї фази завершено. Деякі вузли можуть стати постійно тупиковими посередині цього процесу, і їх позначення таким чином, щоб DFS ніколи не відвідував їх повторно, є ще однією важливою оптимізацією бухгалтерського обліку, яка запобігає повторному марному дослідженню пошуком.

Альтернативні фази та гарантія завершення

Після того, як блокуючий потік однієї фази повністю насичений, алгоритм повністю відкидає потовий рівневий граф і повертається до пошуку в ширину, будуючи новий рівневий граф з нуля на основі залишніх можливостей, що залишилися після застосованого потоку. Ця альтернація – пошук у ширину для побудови структури, пошук у глибину для її повного використання, а потім ще один пошук у ширину для перебудови – повторюється до тих пір, поки пошук у ширину однієї фази не зможе досягти джерела, при цьому алгоритм зупиняється і накопичений потік є доведеним максимальним. Аргумент щодо правильності ґрунтується на класичній лемі: найкоротша відстань від джерела до кінцевої точки в результуючому графі залежностей не зменшується між фазами, і насправді збільшується після кожної блокуючої фази потоку. Інтуїтивно, коли одна фаза насичує всі найкоротші шляхи певної довжини, будь-які залишки посилюючих шляхів у результуючому графі повинні проходити через більш довгий маршрут, оскільки всі короткі мають щонайменше один вузовий канал. Оскільки відстань найкоротшого шляху обмежена зверху числом вершин і строго збільшується принаймні на одиницю після кожної фази, існує не більше O(V) фаз загалом до того моменту, як відстань повинна перевищити V, що є неможливим, змушуючи алгоритм зупинитися. Це набагато сильніша гарантія завершення, ніж пропонується Edmonds-Karp'ом, оскільки Edmonds-Karp обмежує кількість посилюючих шляхів безпосередньо до O(V разів E) замість обмеження кількості фаз, де кожна фаза алгоритму Dinic може одночасно обробляти потенційно багато шляхів. Множення O(V) межі фази на вартість кожного пошуку у ширину плюс блокуючий потік – O(E) – дає загальну складність O(V квадрат * E), і на щільних або дуже зв'язаних графах це може бути значне практичне покращення, особливо оскільки багато реальних мереж потоків мають значно менше фаз, ніж найгірний випадок у реальності.

Де алгоритм Дініку займає місце серед методів максимального потоку

Алгоритм Дініку належить до родини методів максимального потоку, що походить від методу Форда-Фулкерона, загальної рамки повторного пошуку шляхів з посиленням у граничному графі до тих пір, поки вони не залишаться. Простий алгоритм Форда-Фулкерона, який використовує випадковий вибір шляхів, наприклад, глибинний пошук без дисципліни шарування, може погано працювати на графах з ірраціональними або погано вибраними значеннями місткості, а іноді навіть не завершуватися в патологічних випадках із цілочисельною місткістю, якщо реалізований без обережності. Алгоритм Едмондса-Карпа вирішує проблему завершення шляхом вимагання найкоротших шляхів з посиленням, але за це гарантування платить повторними пошуками всього графа. Алгоритм Дініку підтримує дисципліну пошуку найкоротшого шляху, що робить алгоритм Едмондса-Карпа правильним, одночасно усереднюючи вартість пошуку на багато шляхів за фазу, тому його склад строго покращується порівняно з алгоритмом Едмонса-Карпа для загальних графів. Варто зазначити, що на графах із одиничною місткістю, такими як ті, що виникають у задачах бінарного відповідного призначення, алгоритм Дініку досягає ще кращого обмеження O(Е * квадратний корінь з V), що пояснює, чому він лежить в основі ефективних алгоритмів бінарного відповідного призначення, таких як Hopcroft-Karp. Пізніші удосконалення вивели теорію максимального потоку ще далі, включаючи реалізації за допомогою link-cut tree, які досягають O(V * Е * log V) і, значно пізніше, алгоритми майже лінійного часу для максимального потоку на загальних графах, виявлені у 2020-х роках. Незважаючи на це, алгоритм Дініку залишається основним інструментом в конкурентному програмуванні та поширеною базовою лінією в виробничих системах завдяки своїй двофазній структурі: BFS шарування, за яким слідує DFS блокування потоку, яка є концептуально чистою, відносно простою в правильній реалізації та достатньо швидкою на практиці для більшості мереж потоків, які зустрічаються поза екстремальними теоретичними найгіршими випадками. Вивчення його особливо уважно також сприяє розвитку сильного розуміння того, як шарова структури графів і усереднене ведення запису про покажчики можуть перетворити наївний пошук з квадратичною швидкістю на доказово більш щільне обмеження.

Часті запитання

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Dinic's Algorithm for Maximum Flow і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.