Алгоритм Едмондса — Карпа

Алгоритм Едмондса — Карпа розв'язує задачу знаходження максимального потоку в транспортній мережі. Алгоритм являє собою окремий випадок методу Форда-Фалкерсона і працює за час ${\displaystyle O(|V||E|^{2})}$. Вперше був опублікований в 1970 році радянським вченим Ю. А. Деніцом. Пізніше, в 1972 році, був незалежно відкритий Едмондсом і Карпом. Алгоритм Дініца подає додаткові підходи для зменшення часу до ${\displaystyle O(|V|^{2}|E|)}$.

Алгоритм

Алгоритм Едмондса-Карпа — це варіант алгоритму Форда-Фалкерсона, при якому на кожному кроці вибирають найкоротший доповнювальний шлях з ${\displaystyle s}$ в ${\displaystyle t}$ залишкової мережі (вважаючи, що кожне ребро має одиничну довжину). Найкоротший шлях знаходимо пошуком в ширину.

Опис

• Обнуляємо всі потоки. Залишкова мережа спочатку збігається з початковою мережею.
• У залишковій мережі знаходимо найкоротший шлях з джерела в стік. Якщо такого шляху немає, зупиняємося.
• Пускаємо через знайдений шлях (він називається збільшувальним шляхом або збільшувальним ланцюгом) максимально можливий потік:
  • На знайденому шляху в залишковій мережі шукаємо ребро з мінімальною пропускною здатністю ${\displaystyle c_{\min }}$
  • Для кожного ребра на знайденому шляху збільшуємо потік на ${\displaystyle c_{\min }}$ , а в протилежному йому — зменшуємо на ${\displaystyle c_{\min }}$
  • Модифікуємо залишкову мережу. Для всіх ребер на знайденому шляху, а також для протилежних їм ребер, обчислюємо нову пропускну здатність. Якщо вона стала ненульовою, додаємо ребро до залишкової мережі, а якщо обнулилась, стираємо його.
• Повертаємося на крок 2.

Щоб знайти найкоротший шлях в графі, використовуємо пошук в ширину:

• Створюємо чергу вершин О. Спочатку О складається з єдиної вершини s.
• Відмічаємо вершину s як відвідану, без предка, а всі інші як невідвідані.
• Поки черга непорожня, виконуємо наступні кроки:
  • Видаляємо першу в черзі вершину u.
  • Для всіх ребер (u, v), що виходять з вершини u, таких що вершина v ще не відвідана, виконуємо наступні кроки:
    • Відзначаємо вершину v як відвідану, з предком u.
    • Додаємо вершину v в кінець черги.
    • Якщо v=t, виходимо з обох циклів: ми знайшли найкоротший шлях.
• Якщо чергу порожня, повертаємо відповідь, що шляху немає взагалі і зупиняємося.
• Якщо ні, йдемо від t до s, щоразу переходячи до предка. Повертаємо шлях у зворотному порядку.

Псевдокод

algorithm EdmondsKarp input: C[1..n, 1..n] (Ємність матриці) E[1..n, 1..?] (Сусідні листи) s (Джерело) t (Стік) output: f (Значення максимальної витрати) F (Матриця дає правової потік з максимальним значенням) f := 0 (Початковий потік дорівнює нулю) F := array(1..n, 1..n) (Залишкова ємність від u до v це C[u,v] - F[u,v]) forever m, P := BreadthFirstSearch(C, E, s, t, F) if m = 0 break f := f + m (Поверніться до пошуку, і записати потік) v := t while v ≠ s u := P[v] F[u,v] := F[u,v] + m F[v,u] := F[v,u] - m v := u return (f, F) 

algorithm BreadthFirstSearch input: C, E, s, t, F output: M[t] (Знайшли ємність шляху) P (Батьківська таблиця) P := array(1..n) for u in 1..n P[u] := -1 P[s] := -2 (Переконайтеся, що джерело не виявлено) M := array(1..n) (Потужність знайденого шляху до вузла) M[s] := ∞ Q := queue() Q.offer(s) while Q.size() > 0 u := Q.poll() for v in E[u] (Якщо є вільна ємність та v не зустрічався у пошуку) if C[u,v] - F[u,v] > 0 and P[v] = -1 P[v] := u M[v] := min(M[u], C[u,v] - F[u,v]) if v ≠ t Q.offer(v) else return M[t], P return 0, P 

псевдо код Едмондса-Карпа з використанням суміжних вузлів.

algorithm EdmondsKarp input: graph (Графік списку суміжності вузлів з продуктивністю, потік, зворотній і напрямлений) s (Джерело) t (Стік) output: flow (Максимальне значення потоку) flow := 0 (Початковий потік дорівнює нулю) q := array(1..n) (Ініціалізація q, як графу довжину) while true qt := 0(Змінна для проходу по всіх відповідним ребрам) q[qt++] := s (Ініціалізація початкового масиву) pred := array(q.length) (Ініціалізація попереднього списку з графом довжини) for qh=0;qh < qt && pred[t] == null cur := q[qh] for (graph[cur]) (Прохід по всім ребрам) Edge[] e := graph[cur] (Кожне ребро має бути пов'язане з ємністю) if pred[e.t] == null && e.cap > e.f pred[e.t] := e q[qt++] : = e.t if pred[t] == null break int df := MAX VALUE (Ініціалізація до максимального значення) for u = t; u != s; u = pred[u].s df := min(df, pred[u].cap - pred[u].f) for u = t; u != s; u = pred[u].s pred[u].f  := pred[u].f + df pEdge := array(PredEdge) pEdge := graph[pred[u].t] pEdge[pred[u].rev].f := pEdge[pred[u].rev].f - df; flow := flow + df return flow 

Складність

У процесі роботи алгоритм Едмондса — Карпа буде знаходити кожен доповнюючий шлях за час ${\displaystyle O(E)}$. Нижче ми доведемо, що загальне число збільшень потоку, що виконується даним алгоритмом, становить ${\displaystyle O(VE)}$. Таким чином, складність алгоритму Едмондса — Карпа дорівнює ${\displaystyle O(VE^{2})}$.

Доведення

Назвемо відстанню від вершини ${\displaystyle x}$ до вершини ${\displaystyle y}$ довжину найкоротшого шляху від ${\displaystyle x}$ до ${\displaystyle y}$ в залишковій мережі. Якщо такого шляху немає, будемо вважати відстань нескінченною. Будемо говорити, що ${\displaystyle y}$ наблизився до ${\displaystyle x}$ (віддалився від ${\displaystyle x}$), якщо відстань від ${\displaystyle x}$ до ${\displaystyle y}$ зменшилася (збільшилася). Будемо говорити, що ${\displaystyle y}$ ближче до ${\displaystyle x}$ (далі від ${\displaystyle x}$), ніж ${\displaystyle z}$, якщо відстань від ${\displaystyle x}$ до ${\displaystyle y}$ менше (більше), ніж відстань від ${\displaystyle x}$ до ${\displaystyle z}$.

Лема

У ході роботи алгоритму жодна вершина ніколи не наближається до початку.

Доказ. Нехай це не так, тоді при деякому збільшенні потоку деякі вершини наблизилися до джерела. Назвемо їх неправильними. Виберемо ту з неправильних вершин, яка після збільшення потоку виявилася ближче всіх до джерела (якщо таких більше однієї, то будь-яку з них). Позначимо вибрану вершину через v. Розглянемо найкоротший шлях від s до v. Позначимо передостанню вершину на цьому шляху через u, таким чином, шлях має вигляд s -…- uv. Оскільки u ближче до s, ніж v, а v — найближча до s з неправильних вершин, u — вершина правильна. Позначивши відстані від s до u і v до і після збільшення потоку відповідно через ${\displaystyle d_{u}\ }$, ${\displaystyle d_{u}^{'}}$, ${\displaystyle d_{v}\ }$, ${\displaystyle d_{v}^{'}}$, маємо:

${\displaystyle d_{v}^{'}<d_{v}}$

${\displaystyle d_{u}^{'}\geq d_{u}}$

${\displaystyle d_{v}^{'}=d_{u}^{'}+1}$

,звідки

${\displaystyle d_{v}\geq d_{u}+2}$

Отже, до збільшення потоку ребро (u, v) було відсутнім в залишковій мережі. Щоб воно з'явилося, збільшуваний шлях повинен був містити ребро (v, u). Але в алгоритмі Едмондса — Карпа збільшуємий шлях завжди найкоротший, отже,

${\displaystyle d_{v}=d_{u}+1}$

, що суперечить попередній нерівності. Значить, наше припущення було невірним. Лема доведена.

Назвемо критичним те з ребер збільшуючого шляху, у якого залишкова пропускна здатність мінімальна. Оцінимо, скільки разів якесь ребро (u, v) може стати критичним. Нехай це відбулося на ітерації ${\displaystyle t_{1}}$, а в наступній раз на ітерації ${\displaystyle t_{2}}$. Позначаючи через ${\displaystyle D_{y}(t)}$ відстань від s до y на ітерації t, маємо:

${\displaystyle D_{v}(t_{1})=D_{u}(t_{1})+1}$

${\displaystyle D_{v}(t_{2})=D_{u}(t_{2})+1}$

Зауважимо, що на ітерації ${\displaystyle t_{1}}$ критичне ребро зникає із залишкової мережі. Щоб до моменту ітерації ${\displaystyle t_{2}}$ребро (u, v) в ній знову з'явилося, необхідно, щоб на якійсь проміжній ітерації ${\displaystyle t_{3}}$ був обраний збільшуючий шлях, що містить ребро (v, u).

Отже,

${\displaystyle D_{u}(t_{3})=D_{v}(t_{3})+1}$

Використовуючи раніше доведену лемму, отримуємо:

${\displaystyle D_{v}(t_{2})=D_{u}(t_{2})+1\geq D_{u}(t_{3})+1=D_{v}(t_{3})+2\geq D_{v}(t_{1})+2}$

Оскільки спочатку ${\displaystyle D_{v}>0}$ (інакше v = s, але ребро, провідне в s, не може з'явитися на найкоротшому шляху з s в t), і завжди, коли ${\displaystyle D_{v}}$звичайно, воно менше V (найкоротший шлях не містить циклів, і, отже, містить менше V ребер), ребро може виявитися критичним не більше ${\displaystyle {\frac {(V-1)-1}{2}}+1=V/2}$ раз. Оскільки кожен збільшуючий шлях містить хоча б одне критичне ребро, а всього ребер, які можуть колись стати критичними, ${\displaystyle 2E}$(всі ребра вихідної мережі і їм протилежні), то ми можемо збільшити шлях не більше EV раз. Отже, кількість ітерацій не перевищує O (EV), що потрібно було довести.

Приклад

Нехай задана мережа з витоком у вершині ${\displaystyle A}$ і стоком в вершині ${\displaystyle G}$. На малюнку парою ${\displaystyle f/c}$ позначений потік по цьому ребру і його пропускна спроможність.

Пошук в ширину

Опишемо пошук в ширину на першому кроці.

1. Черга складається з єдиної вершини A. Пройдена вершина A. Предків немає.
2. Черга полягає (від початку до кінця) з вершин B і D. Пройдені вершини A, B, D. Вершини B D мають предка А.
3. Черга складається з вершин D і C. Пройдені A, B, C, D. Вершини B, D мають предка А, вершина C — предка B.
4. Черга складається з вершин C, E, F. Пройдені A, B, C, D, E, F. Вершини B, D мають предка А, вершина C — предка B, вершини E, F — предка D.
5. Вершина C видаляється з черги: ребра з неї ведуть тільки у вже пройдені вершини .
6. Можна знайти ребро (E, G) і цикл зупиняється. У черзі вершини (F, G). Відвідані всі вершини . Вершини B, D мають предка А, вершина C — предка B, вершини E, F — предка D, вершина G — предка E.
7. Йдемо по предкам: G->E->D->A. Повертаємо пройдений шлях у зворотному порядку: А->D->E->G.

Зауважимо, що в чергу послідовно додавали вершини, досяжні з A рівно за 1 крок, рівно за 2 кроки, рівно за 3 кроки. Крім того, предком кожної вершини є вершина, досяжна з A рівно на 1 крок швидше.

Основний алгоритм

Пропускна здатність шляху	шлях
${\displaystyle \min(c_{f}(A,D),c_{f}(D,E),c_{f}(E,G))=}$ ${\displaystyle \min(3-0,2-0,1-0)=}$ ${\displaystyle \min(3,2,1)=1}$	${\displaystyle A,D,E,G}$
${\displaystyle \min(c_{f}(A,D),c_{f}(D,F),c_{f}(F,G))=}$ ${\displaystyle \min(3-1,6-0,9-0)=}$ ${\displaystyle \min(2,6,9)=2}$	${\displaystyle A,D,F,G}$
${\displaystyle \min(c_{f}(A,B),c_{f}(B,C),c_{f}(C,D),c_{f}(D,F),c_{f}(F,G))=}$ ${\displaystyle \min(3-0,4-0,1-0,6-2,9-2)=}$ ${\displaystyle \min(3,4,1,4,7)=1}$	${\displaystyle A,B,C,D,F,G}$
${\displaystyle \min(c_{f}(A,B),c_{f}(B,C),c_{f}(C,E),c_{f}(E,D),c_{f}(D,F),c_{f}(F,G))=}$ ${\displaystyle \min(3-1,4-1,2-0,0--1,6-3,9-3)=}$ ${\displaystyle \min(2,3,2,1,3,6)=1}$	${\displaystyle A,B,C,E,D,F,G}$

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

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

Покращеною версією алгоритму Едмондса-Карпа є алгоритм Дініца, що вимагає ${\displaystyle O(|V|^{2}|E|)}$ операцій.

Назвемо допоміжною безконтурною мережею графу G з джерелом s його підграф, що містить тільки такі ребра (u, v), для яких мінімальна відстань від s до v на одиницю більше мінімальної відстані від s до u.

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

• Будуємо мінімальну безконтурну мережу остаточного графу.

• Поки в мережі є шлях із s в t, виконати наступні кроки:
  • Знаходимо найкоротший шлях з s в t. Якщо його немає, вийти з циклу.
  • На знайденому шляху в остаточній мережі шукаємо ребро з мінімальною пропускною здатністю ${\displaystyle c_{\min }}$.
  • Для кожного ребра на знайденому шляху збільшуємо потік на ${\displaystyle c_{\min }}$, а в протилежному йому — зменшуємо на ${\displaystyle c_{\min }}$.
  • Видаляємо всі ребра, які досягли насичення.
  • Видаляємо всі глухі кути (тобто вершини, крім стоку, звідки не виходить ребер, і вершини, крім джерела, куди ребер не входить) разом з усіма інцидентними їм ребрами.
  • Повторюємо попередній крок, поки є що видаляти.
• Якщо знайдений потік ненульовий, додаємо його до загального потоку і повертаємося на крок 1.

Посилання

• Реалізація алгоритму Эдмондса-Карпа на C++ на сайті e-maxx.ru [ 28 квітня 2015 у Wayback Machine.]
• Реалізація пошуку максимального потоку методом Эдмондса-Карпа на Java [ 18 квітня 2015 у Wayback Machine.]