Алгоритм розміщення позначок для задачі про максимальний (від s до t) потік

А. Розміщення позначок. Вершина може перебувати в одному із трьох станів:

- вершині присвоєна позначка й вершина переглянута (тобто вона має позначку і всі суміжні з нею вершини "опрацьовані");

- позначка присвоєна, але вершина не переглянута (тобто вона має позначку, але не всі суміжні з нею вершини опрацьовані);

- вершина не має позначки.

Позначка вершини x(i) складається з двох частин і має один із двох типів: (+х(j), m) або (-x(i), m). Частина +х(j) позначки першого типу означає, що потік допускає збільшення вздовж дуги (x(j), x(i)). Частина -x(j) позначки іншого типу означає, що потік може бути зменшений вздовж дуги (х(і),х(j)). В обох випадках m задає максимальну величину додаткового потоку, що може протікати від s до х(і) вздовж побудованого ланцюга потоку, що збільшується. Присвоєння позначки вершині x(i) відповідає знаходженню ланцюга потоку, що збільшується, від s до х(і). Спочатку всі вершини не мають позначок.

Крок 1. Присвоїти вершині s позначку (+s, m(s) = нескінченність). Вершині s присвоїти позначку і вважати її переглянутою, всі інші вершини без позначок.

Крок 2. Взяти деяку непереглянуту вершину з позначкою; нехай її позначка буде (+- х(k), m(x(i)) (+- позначає, що перед х(k) може стояти як плюс, так і мінус).

(1) Кожній позначеній вершині x(j), що належить G(х(l)), для якої

с(і, j)<q(j, i), присвоїти позначку (-х(і), m(х(j))), де

m(x(j))=min[m(x(i)), q(i, j) – c(i,j)].

(II) Кожній непозначеній вершині x(j), що належить D(x), для якої с(i,j)>0, присвоїти позначку (-х(і), m(х(j))), де

m(x(j))=min[m(x(i)), c(j, i)].

(Тепер вершина х(і) і позначена, і переглянута, а вершини x(j), яким присвоєні позначки у (I) і (II), є непереглянутими.) Позначимо, що вершина x(i) переглянута.

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