Изменения

Перейти к: навигация, поиск

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

141 байт добавлено, 2 май
Алгоритм
* '''Шаг 2'''. Для каждого ребра зададим поток равный <tex>0</tex>.
* '''Шаг 3'''. Найдем произвольный максимальный поток(любым алгоритмом нахождения максимального потока), построим для него остаточную сеть, где каждому ребру будет соответствовать величина <tex>a(u,v) \cdot (c(u,v) - f(u,v))</tex>.
* '''Шаг 4'''. При помощи [[Алгоритм Форда-Беллмана| алгоритма Форда-Беллмана]] найдем отрицательный цикл в построенной сети(отрицательный цикл ищется по стоимости ребра, т.е. ребра имеют вес <tex>a(u,v)</tex>). Если отрицательный цикл не нашелся {{---}} перейдем к '''шагу 6'''.
* '''Шаг 5'''. Избавимся от отрицательного цикла, для этого пустим по нему максимально возможный поток. Величина потока равна минимальной остаточной пропускной способности в цикле. Перейдем к '''шагу 4'''.
* '''Шаг 6'''. Отрицательных циклов в остаточной сети нет, значит, максимальный поток минимальной стоимости найден.
Анонимный участник

Навигация