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

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

Алгоритм

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

Опис

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

Складність

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

Доведення

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

Лема

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

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

,звідки

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

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

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

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

Отже,

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

Оскільки спочатку (інакше v = s, але ребро, провідне в s, не може з'явитися на найкоротшому шляху з s в t), і завжди, коли звичайно, воно менше V (найкоротший шлях не містить циклів, і, отже, містить менше V ребер), ребро може виявитися критичним не більше раз. Оскільки кожен збільшуючий шлях містить хоча б одне критичне ребро, а всього ребер, які можуть колись стати критичними, (всі ребра вихідної мережі і їм протилежні), то ми можемо збільшити шлях не більше ЕV раз. Отже, кількість ітерацій не перевищує O (EV), що потрібно було довести.

Приклад

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

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

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

  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 крок швидше.

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

Пропускна здатність шляху шлях












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

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

Покращеною версією алгоритму Едмондса-Карпа є алгоритм Дініца, що вимагає операцій.

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

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

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

Посилання

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