1. Построить произвольный поток j в сети <G; c> (можно и нулевой).
2. Построить полный
поток. Если поток j не полный, то в сети
существует путь из v0 в vn, все дуги которого не насыщены.
Увеличивая потоки через все дуги такого пути P на величину получаем путь,
некоторая дуга которого является насыщенной. Такую операцию следует повторять
до тех пор, пока не получится полный поток.
3. Построить максимальный поток.
А. Начальные пометки. Присвоить источнику пометку 0: l(v1) = 0; а остальным вершинам пометку ¥. Следующий шаг повторять до тех пор, пока в результате его выполнения не будет помечен сток vn либо пока не перестанут появляться новые пометки.
Б. Пересчет пометок. Для каждой помеченной вершины vi, пометить символом +i все непомеченные вершины v (l(v) = ¥), для которых дуги (vi; v) ненасыщенные (т.е. j(vi; v) < c(vi; v)), и символом -i все непомеченные вершины, для которых j(v; vi) > 0.
В. Увеличение
потока. Если сток vn не получает новую пометку, то закончить
работу алгоритма (максимальный поток найден), в противном случае существует
цепь (заметьте: в общем случае - не путь!) v0 ®…® vn, все вершины которой
помечены. Если ориентация дуги a = (vi; vj) совпадает с
направлением прохождения цепи, будем обозначать ее , в противном
случае - .
Если l(vj)
= +i (= (vi; vj)), то положить l(a) = c(a) -j(a). Если l(vj) = -i (
= (vj
; vi)), то положить l(a) = j(a). Пусть
(минимум вычисляется
по всем дугам, составляющим указанную цепь). По каждой дуге
поток увеличить
на
, а по каждой дуге
поток уменьшить
на
. (При этом величина потока в сети W(j) увеличится на e). Перейти к шагу А.