147
правок
Изменения
Нет описания правки
==Задача==
Задача о потоке минимальной стоимости состоит в нахождении среди всех [[Определение сети, потока|потоков]] данной величины наименее затратного.
==Идея==
В основе алгоритма лежит [[Теорема Форда-Фалкерсона о потоке минимальной стоимости|теорема Форда-Фалкерсона о потоке минимальной стоимости]]. На каждой итерации алгоритма будем находить путь минимальной стоимости из <tex>s</tex> в <tex>t</tex> и дополнять поток вдоль этого пути. Выбирать алгоритм для поиска кратчайших путей следует с учетом того, что в ходе алгоритма появляются ребра отрицательного веса.
