Постановка задачі. Розглянемо граф (див. л.р

(4.1)

де - можливий потік через дугу (i, j)

- задане значення пропускної здатності для дуги (i, j).

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

(4.2)

Задача полягає в визначенні таких дугових потоків, щоб загальний потік з джерела s в стік t був максимальним:

(4.3)

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

 

g_{i ,} g_j - кількість одиниць потоку

Позитивна позначка збільшує потік по дузі b_ij, але так, щоб сумарний потік не перевищив ; негативна позначка зменшує потік по дузі, але так, щоб він не став негативним.

Вузли помічаються послідовно від 1 до n.

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

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

Алгоритм закінчує роботу, якщо жоден вузол мережі вже не може бути позначений з джерела.