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

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

Алгоритм

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

Опис

Обнуляємо всі потоки. Залишкова мережа спочатку збігається з початковою мережею.
У залишковій мережі знаходимо найкоротший шлях з джерела в стік. Якщо такого шляху немає, зупиняємося.
Пускаємо через знайдений шлях (він називається збільшувальним шляхом або збільшувальним ланцюгом) максимально можливий потік:
- На знайденому шляху в залишковій мережі шукаємо ребро з мінімальною пропускною здатністю $c_{\min}$
- Для кожного ребра на знайденому шляху збільшуємо потік на $c_{\min}$ , а в протилежному йому — зменшуємо на $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

Складність

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

Доведення

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

Лема

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

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

d_{v}^{'} < d_{v}

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

d_{v}^{'} = d_{u}^{'} + 1

,звідки

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

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

d_{v} = d_{u} + 1

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

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

D_{v} (t_{1}) = D_{u} (t_{1}) + 1

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

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

Отже,

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

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

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

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

Приклад

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

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

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

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

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

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

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

$\min (c_{f} (A, D), c_{f} (D, F), c_{f} (F, G)) =$ $\min (3 - 1, 6 - 0, 9 - 0) =$ $\min (2, 6, 9) = 2$	$A, D, F, G$

$\min (c_{f} (A, B), c_{f} (B, C), c_{f} (C, D), c_{f} (D, F), c_{f} (F, G)) =$ $\min (3 - 0, 4 - 0, 1 - 0, 6 - 2, 9 - 2) =$ $\min (3, 4, 1, 4, 7) = 1$	$A, B, C, D, F, G$

$\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)) =$ $\min (3 - 1, 4 - 1, 2 - 0, 0 - - 1, 6 - 3, 9 - 3) =$ $\min (2, 3, 2, 1, 3, 6) = 1$	$A, B, C, E, D, F, G$

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

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

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

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

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

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

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

Посилання

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

Зміст