3.4.3. Алгоритм построения максимального потока в транспортной сети

Алгоритм построения максимального потока в транспортной сети D:

Шаг 1. Полагаем i = 0. Пусть j0 - любой допустимый поток в транспортной сети D. (например, полный; можно начинать с нулевого потока: j0 (x), x Î X).

Шаг 2. По сети D и потоку ji строим орграф приращений I(D, ji).

Шаг 3. Находим простую цепь hi, являющуюся минимальным путем из v1 в vn в нагруженном орграфе I(D, ji) (например, используя алгоритм Форда - Беллмана). Если длина этой цепи равна ¥, то поток ji максимален, и работа алгоритма закончена. В противном случае увеличиваем поток вдоль цепи hi на максимально допустимую величину ai > 0, где ai Î Z (прибавляя ее для каждой дуги x Î X, через которую проходит цепь hi, к уже имеющейся величине потока по дуге x, если направления x и hi совпадают, и, вычитая, если направления x и hi противоположны).

Пример 92.

Выяснить является ли полный поток максимальным (рис. 51), если нет, то дополнить его до максимального.

Решение.

Для решения используем алгоритм Форда-Беллмана нахождения минимального пути в нагруженном орграфе.

Построим матрицу длин дуг C(D) и l-матрицу (табл. 69).

Таблица 69

	v1	v2	v3	v4	v5	v6
v1	¥	¥	0	¥	¥	¥		0	0	0	0	0	0
v2	0	¥	¥	¥	0	¥		¥	¥	0	0	0	0
v3	0	0	¥	0	0	¥		¥	0	0	0	0	0
v4	¥	0	0	¥	¥	0		¥	¥	¥	¥	¥	0
v5	¥	0	0	¥	¥	0		¥	¥	¥	0	0	0
v6	¥	¥	¥	0	0	¥		¥	¥	¥	¥	0	0

Поскольку , то существует нулевой путь из источника v1 в сток v6.

Получаем, что k1 = 4. Таким образом, минимальное число дуг в пути среди всех нулевых путей из v1 в v6 в орграфе приращений равняется 4. Определим теперь последовательность номеров i1, i2, i3, i4, i5,где i1 = 6.

Получаем, что в качестве такой последовательности надо взять номера 1, 3, 2, 5, 6, так как

Тогда v1v3v2v5v6 – искомый нулевой путь из v1 в v6 . Дуги, совпадающие по направлению с дугами исходной транспортной сети помечаем знаком «+», не совпадающие – знаком «-».

Получаем, Теперь необходимо найти величину, которую будем перемещать по полученному контуру. Для этого, каждому ребру в контуре поставим в соответствие число a(i, j), которое находим по следующему правилу: если направление ребра (i, j) в контуре совпадает с направлением ребра x в транспортной сети, то a(i, j)=с(х)-j(х); если направление ребра в контуре не совпадает с направлением ребра в транспортной сети, то a(i, j)=j(х). Итак, из чисел a(i, j) найдем минимальное:

min{8-2=6, 2, 6-2=4, 9-4=5}=2.

Перемещаем по контуру 2.

В результате получаем поток, изображенный на рисунке 52.

Заметим, что в полученной транспортной сети не существует пути из источника в сток, по которому возможно пройти. Следовательно, построенный поток в транспортной сети является полным и j = 11. Проверим, является ли он максимальным.

Построим матрицу длин дуг C(D) и l-матрицу (табл. 70).

Таблица 70

	v1	v2	v3	v4	v5	v6
v1	¥	¥	0	¥	¥	¥		0	0	0	0	0	0
v2	0	¥	0	¥	0	¥		¥	¥	¥	¥	¥	¥
v3	0	¥	¥	¥	¥	¥		¥	0	0	0	0	0
v4	¥	0	0	¥	¥	0		¥	¥	¥	¥	¥	¥
v5	¥	0	0	¥	¥	0		¥	¥	¥	¥	¥	¥
v6	¥	¥	¥	0	0	¥		¥	¥	¥	¥	¥	¥

Так как , то нулевого пути из v1 в v6 не существует.