2 Метод Форда-Фалкерсона

У будь-якій мережі існує максимальний потік. Величина максимального потоку дорівнює пропускній здатності мінімального розрізу.

Потік, обчислений за допомогою алгоритму Форда-Фалкерсона має максимальну величину, а розріз (x, x), де x-безліч помічених вершин, має мінімальну пропускну здатність.

Алгоритм Форда-Фалкерсона для знаходження максимального потоку в мережі складається з двох процедур:

1) Процедура помічення вершин

2) Процедура зміни потоку

2.1 Процедура помічення вершин.

Обробка i-й вершини з позначкою (x, e) полягає в тому, що з вершини i позначаються суміжні непомеченние вершини за наступним правилом:

- Якщо дуга направлена ​​з i в j та потік по цій дузі (fij) менше пропускної здатності дуги (cij), то вершині j присвоюється мітка (i +, min (e, cij-fij)).

- Якщо дуга направлена ​​з j в i та потік по цій дузі (fji) більше нуля, то вершині j присвоюється мітка (i-, min (e, fji)).

Ця процедура завжди починається з помічення та обробки витоку. Він позначається особливою міткою. Процес помічення закінчується в двох випадках:

1) Жодну вершину більше не можна помітити, але стік непомічений. Це значить, що знайдений потік - максимальний і алгоритм зупиняється.

2) Позначаю стік. В цьому випадку проводиться зміна потоку.

2.2 Процедура зміни потоку.

Якщо стік отримав мітку (k +, d), то потоки будуть змінюватися на величину d таким чином:

- Якщо ми перебуваємо в вершині j з міткою (i +, x), то додаємо d до fij і переходимо в вершину i.

- Якщо ми перебуваємо в вершині j з міткою (i-, x), то віднімаємо d з fij і переходимо в вершину i.

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

2.3 Базовий алгоритм Форда-Фалкерсона.

Ford_Fulkerson (G, s, t)

1 for (для) кожного ребра (u, v) ∈ E [G]

2 do f [u, v] ← 0

3 f [v, u] ← 0

4 while існує шлях р з s в t в залишкової мережі Gf

5 do Cf (p) ← min {Cf (u, v): (u, v) належить р}

6 for (для) кожного ребра (u, v) in p

7 do f [u, v] ← f [u, v] + Cf (р)

8 f [v, u] ← - f [u, v]

Рис.2.3. Базовий алгоритм Форда-Фалкерсона

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

2. В залишкової мережі знаходимо будь-який шлях з джерела в стік. Якщо такого шляху немає, зупиняємося.

3. Пускаємо через знайдений шлях максимально можливий потік.

4. На знайденому шляху в залишкової мережі шукаємо ребро з мінімальною пропускною здатністю cmin.

5. Для кожного ребра на знайденому шляху збільшуємо потік на cmin, а в протилежному йому - зменшуємо на cmin.

6. Модіфікуємо залишкову мережу. Для всіх ребер на знайденому шляху, а також для протилежних їм ребер, обчислюємо нову пропускну здатність. Якщо вона стала ненульовою, додаємо ребро до залишкової мережі.

3. Написати програму сортування одномірного масиву методом злиття з мінімальною кількістю порівнянь.