Введем граф приращения следующим образом:
Вершины в графе те же, что и в сети, а дуг в два раза больше, причем соответствуют нормальная дуга и обращенная дуга , длины которых, определены правилом:
Поток будет максимальным, если в нет путей из в нулевой длины.
Задание начального допустимого потока .
.
Построение графа приращений .
Определение кратчайшего расстояния в и соответствующей ему цепи кратчайшего пути.
Если , то выполнение п.6, иначе выполнение п.10.
Строим простой поток по цепи .
(в общем случае: ).
.
Переходим к пункту 3.
Окончание алгоритма.
Алгоритм отыскания максимального потока в произвольных сетях с ограниченными пропускными способностями
Если нам известен некий допустимый поток в сети , то берем его в качестве начального и используем предыдущий алгоритм.
Рассмотрим вопрос нахождения начального допустимого потока:
Для нахождения начального потока строим вспомогательную сеть : , в которой множество вершин включает, кроме , еще 2 дополнитльные вершины и , а множество дуг определяется следующим образом: каждой дуге будет соответствовать 3 дуги:
, ,
Кроме того добавляем дугу
Пропускные способности определяются следующим образом:
, где - очень большое целое число.
Тогда сеть - транспортная.
Определение. Допустимый поток из нового источника в новый сток называется насыщенным, если для всех дуг из (или ).
Теорема. Если насыщенный поток из , то поток в сети является допустимым из в , а его величина равняется .
Если - максимальный, но ненасыщенный в сети , то в нет допустимых потоков вообще.