Итерация 2

Теперь просматриваем остаточные пропускные способности b_ij-x_ij (выделены голубым цветом или жирным шрифтом на рис.1). источнику S приписываем пометку [∞;-]. Из источника S предпочтительнее двигаться в вершину 1, вершине 1 приписываем пометку [2;S]. Из вершины 1 идем в вершину 2; вершине 2 приписываем пометку [2;1], так как q₂=min[q₁;b₁₂-x₁₂]=2. из вершины 2 идем в вершину 3. для третьей вершины q₃=min[q₂;b₂₃-x_23]=min[2;1]=1; вершине 3 приписываем пометку [1;2].из вершины 3 идем в сток. Стоку приписываем пометку [1;3]. Минимальное изменение дуговых потоков равно 1, т. е. изменение дуговых потоков будет x₃₁=1, x₁₂=1, x₂₃=1, x₃₁=1. максимальный поток равен 2+1=3 ед. дуги получают следующие пометки, показанные на рисунке 3.

[0,4] рис.3 вторая итерация

[0,3] 3

[2,2] 0

[1, 2] [2,3]

[1,1]

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

[0,1]

[1,2] 1