Итерация 4

Приписываем вершине S пометку [∞;-]. Из вершины S направляемся в вершину 2:q₂=min[q_s;b_s2-x_s2]=min[∞;1]=+1; вершине 2 приписываем пометку [1;S]. из вершины 2 мы можем попасть в сток t, только пройдя по обратной дуге в вершину 1, а затем в сток t. Определим пометку для вершины 1 в данном случае: q₁=min[q₂,x₁₂]=min[1;4]=+1, т.е. вершине 1 приписываем пометку [1;2]. Для вершины t:q_t=min[q₁;u_1,t-x_1t]=min[1;1]=+1; вершине t приписываем пометку [1;1]. Изменение дуговых потоков для x_s2, x₁₂, x_1t равно 1. потоки по этим дугам будут соответственно x_s2=2, x₁₂=0, x_1t=2; максимальный поток из S в t равен 4+1=5 ед. Дуги получают пометки [изменяются пометки только на дугах (S,2); (1,2) и (1, t)], показанные на рисунке 5.

[0,4] рис.5 Четвертая итерация

[2,3] 1

[2,2] 0

[2, 2] [3,3]

[1,1]

Поток равен 5 ед.

[0,1]

[1,2] 1