Рис. 11.14д. Улучшенный поток . (4,-25)

Рис. 11.14е. (I) для потока на рис. (д).

Рис. 11.14ж. Улучшенный поток

(17,25) x,

Рис. 11.143. G (I) для потока на рис. (ж).

Рис. 11.14и. Улучшенный поток . (П, 25)

Рис. 11.14K. (I) для потока на рис. (и).

Шаг 3. Обнаружен отрицательный цикл (xg, х^, х^, х^) со стоимостью -10.

Шаг 4. Ь = min [4, И, 19] = 4. Новый поток со стоимостью 512 изображен на рис. 11.14д.

Шаг 2. Граф (), соответствующий новому потоку, изображен на рис. 11.14е.

Шаг 3. Обнаружен отрицательный цикл (х^, Хз, х^ х^, х,) со стоимостью -8.

Шаг 4. б = min [16, 4, 16, 16] = 4.

Новый поток со стоимостью 480 изображен на рис. 11.14ж.

Шаг 2. Получившийся граф G () показан на рис. 11.14з.

Шаг 3. Обнаружен отрицательный цикл (х^, х^, х^, х^, х^, х^, Xi) со стоимостью -4.

Шаг 4. 8 = min (7, 15, 1, 4, 4, 16) = 1.

Новый поток со стоимостью 476 изображен на рис. 11.14 и. Шаг 2. Граф G () изображен на рис. 11.14к.

Шаг 3. Обнаружен отрицательный цикл {х^, х^, х^, х^) со стоимостью -2.

Шаг 4. 8 = min [1, 6, 5] = 1.

Рис. 11.14л. Поток минимальной стоимости.

Новый поток со стоимостью 474 изображен на рис. 11.14л.

В последнем инкрементальном графе нет никаких циклов с отрицательной стоимостью, и поэтому поток, изображенный на рис. 11.14 л, является потоком наименьшей стоимости со значением 20 и его стоимость равна 474.