Шаг 6. Если z = s, то стереть все пометки и вернуться к шагу 1, чтобы вновь начать расставлять пометки, но используя уже улучшенный поток, найденный на шаге 5. Если гф s, то взять а; = Z и вернуться к шагу 5.

2.2. Пример

Рассмотрим граф, изображенный на рис. 11.1, и возьмем в качестве источника вершину х^, а ъ качестве стока - вершину 0:9. Пропускные способности дуг указаны на рисунке. Требуется найти максимальный поток от х^ к Хд.

В качестве начального возьмем поток с нулевыми значениями на всех дугах. Алгоритм работает следующим образом.

Шаг 1. Припишем вершине х^ пометку {х^, оо).

Шаг 2. (I) Множество вершин {xj \ Xj {х-, %ij <; qij, Xj не помечена} есть {х^ х^,

вершине х^ приписывается пометка (+a;i, min [00, 14 - 0], т. е. {+Xi, 14),

вершине х^ приписывается {х-, min [00, 23 - 0]), т. е. (+.1, 23).

(II) Множество вершин {xj \ Xj g Г {х-, > О, х, не помечена) является пустым. Итак, х^ помечена и просмотрена, х^ и Xi помечены и не просмотрены, а все остальные вершины не помечены. Повторяем шаг 2 и первой просматриваем вершину х^.

(I) Множество {xj \х, {х^, < 4ii и х, не помечена} есть {х^.

для Хз пометкой будет {х^, min [14, 10 - 0] = {-{-х^, Ю).

56 Ч 4

Рис. 11.1. Граф из примера 2.2.

Вид потока в конце шага 5 и пометки вершин до их стирания на шаге 6 показаны на рис. 11.2а. Все потоки показаны подчеркиванием.

Стирая пометки у вершин и возвращаясь к шагу 1 для второго прохода, получим следующие новые пометки вершин (помеченные, но не просмотренные вершины просматриваются в порядке возрастания их номеров).

Шаг 3.

Пометкой для Xi будет (+i,

пометкой для х^, будет (+Xi, min [оо, 14 - 4]) = {+Xi, 10),

пометкой для х^ будет (+i, min [оо, 23 - 0]) = (+i, 23);

теперь вершина х^ помечена и просмотрена.

Пометкой для Хз будет (+2> min [10, 10 - 4]) = i+x, 6),

теперь вершина Xj помечена и просмотрена.

Пометкой для х^ будет {-{-Хз, min [6, 12 - 4]) = {+Хз, 6),

пометкой для Xg будет (+3. min [6, 18 - 0]) = {+Хз, 6);

теперь вершина Хз помечена и просмотрена,

вершина х^ также помечена и просмотрена.

(II) Множество {xj \ Xj 6 Г [х^, < О и Xj не помечена} является пустым. Теперь вершины х- и х^ помечены и просмотрены, а Хз и х^ помечены, но не просмотрены.

Беря для просмотра Хз и повторяя шаг 2, придем к следуюш,им пометкам:

для х^ пометкой будет (+з, min [10, 12 - 0]) = {+Хз, 10), для Xg пометкой будет i+Xg, min [10, 18 - 0]) = (+Хз, 10).

Беря для просмотра х^, найдем, что никаких пометок расставить нельзя. Продолжая просмотр с х^, получим следующие пометки:

С+.г 10)

Рис. 11.2а. Потоки и пометки после 1-й итерации. - насыщенные дуги.

(+дг >)

(+л- 23)

Рис. 11.26. Потоки и пометки после 2-й итерации. - насыщенные дуги.