4. Сетевые модели

4.9 Алгоритм отыскания максимального потока минимальной стоимости (двухкритериальная задача в сети)

Алгоритм тот же самый, что и для отыскивания максимального потока, с той разницей, что граф приращения строится иначе и начальный допустимый поток должен иметь минимальную стоимость (для трансортной сети это нулевой поток)

Для построения графа приращений достаточно изменить функцию длины в графе приращения :

,

где стоимость провоза еденицы потока по дуге .