Виклад алгоритму Форда-Фалкерсона

Алгоритм складається з послідовних iтерацiй, які проводяться до тих пір, поки не буде виконуватись ознака оптимальності.

На кожній iтерацiї можна виділити два етапи.

Етап 1 (етап виставлення позначок).

1. В кожний момент часу кожна вершина може знаходитись в одному з трьох положень:

а) непозначена;

б) позначена, але не проглянута;

в) позначена i проглянута.

Загальний вигляд позначки j -ї вершини: [ i+,_j ], або [ i – ,_j ], де i – номер деякої позначеної вершини, при прогляданнi якої була позначена вершина j. Вершина 1 завжди позначена та має позначку [1 +,₁ ], де ₁ рівне + (нескінченності).

2. Проглядання довільної позначеної вершини j полягає у такому:

a) довільна непозначена вершина k, для якої існує дуга (j,k) i має місце нерівність xjk < rjk, отримує позначку вигляду [ j+,k ], де

k = min { _j, r_jk – x_jk };

б) довільна непозначена вершина k, для якої існує дуга (k,j) i має місце умова x_kj >0, отримує позначку вигляду [ j – ,_k ], де

k = min { _j, x_kj }.

3. Виставлення позначок закінчується в одному з двох випадків:

а) вершина з номером n позначена;

б) умова а) не виконується, але жодної вершини більше позначити не можна.

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

Етап 2 (етап зміни потоку).

Потiк в мережі змінюється на величину _n відповідно до правила. Якщо вершина n має позначку [ k+,_n ], де k – номер деякої вершини, то x_kn = x_kn + _n. Якщо позначка має вигляд [ k – ,_n ], то x_nk = x_nk – _n. Переходимо до вершини з номером k. Якщо позначка вершини k має вигляд [ j+,_k ], то x_jk = x_jk + _n; якщо вона дорівнює [ j – ,_k ], то x_kj = x_kj – _n. Подібні дії продовжуємо доти, поки не буде досягнута початкова вершина. В цьому випадку всі старі позначки витираємо i повертаємось до першого етапу.

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

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

Задача про найкоротший шлях в мережi. Метод Мiнтi