Розставляння позначок

Позначка довільної вершини х_i складається з двох частин і може бути двох видів:

(+x_j, d) або (-x_j, d)

де +x_j означає, що потік припускає збільшення уздовж дуги (x_i, x_j); -x_j - потік може бути зменшений уздовж дуги (x_i, x_j); d - максимальний розмір додаткового потоку, що може протікати від S до x_i, уздовж побудованого ланцюга потоку. Вершина може знаходитися в одному із трьох станів:

1. Вершині приписана позначка, і вершина переглянута (тобто вона має позначку і всі суміжні з нею вершини "оброблені").

2. Позначка приписана, але вершина не переглянута (тобто вона має позначку, але не всі суміжні з нею вершини "оброблені").

3. Вершина не має позначки.

Спочатку усі вершини не мають позначок.

Крок 1. Привласнити вершині х_i= S позначку (+ S, ¥).

Крок 2. Взяти деяку не переглянуту вершину x_i із позначкою; нехай її позначка є (±x_k, d(x_i));

а) кожній непозначеній вершині x_j Î F(x_j), для якої x_ij > q_ij,., привласнити позначку

(+x_k, d(x_j)), де d(x_j) = min {d(x_i), q_ij - x_ij};

б) кожній непозначеній вершині x_j Î F^-1(x_j), для якої позначку x_ij > 0, привласнити позначку (-x_j, d(x_j)), де d(x_j) = min {d(x_i), x_ij}.

Тепер вершина x_i і позначена, і переглянута, а вершини позначки яким привласнені, є непереглянутими.

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