Алгоритм пошуку максимального потоку у мережі.

Крок 1. Перенумерувати всі вершини мережі довільним чином, окрім витоку та стоку.

Крок 2. Задати у мережі початковий потік (наприклад, нульовий).

Крок 3. Вершинам мережі приписати цілочислові помітки, а дугам — знаки «+» чи «–» за наступними правилами:

а) вершині-витоку приписати позначку «0»;

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

Якщо вершина є образом поміченої вершини , то вершина отримує мітку, що дорівнює номеру вершини , дуга отримує помітку «+», після чого переходять до розгляду наступної вершини.

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

Процес приписування позначок продовжується доти, доки всі вершини, що задовольняють зазначеним вище умовам, не отримають помітки.

Крок 4. Якщо в результаті приписування поміток вершина-стік не отримала помітки, то потік у мережі є максимальним і задача вирішена, інакше переходять до кроку 5.

Крок 5. Розглянути послідовність вершин , помітка кожної з яких дорівнює номеру наступної за нею вершини, та множину дуг , що з’єднують суміжні вершини з послідовності . Побудувати новий потік за наступною схемою:

а) якщо дуга належить множині та має помітку «+», то потік по цій дузі збільшити на ;

б) якщо дуга належить множині та має помітку «–», то потік по цій дузі зменшити на ;

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

Схема знаходження .

.

Для знаходження переглядають всі дуги, що належать множині та мають позначку «+». Для кожної такої дуги обчислюють різницю між пропускною спроможністю дуги та потоком у цій дузі. З цих значень вибирають найменше та присвоюють .

Для знаходження переглядають всі дуги, що належать множині та мають позначку «–». З цих дуг вибирають дугу з найменшим потоком і значення потоку по цій дузі присвоюють .

Переходять до кроку 3.