Перебор сквозных путей от истока к стоку с вычислением пропускных способностей этих путей. Для работы алгоритма требуется чтобы в структуре сети были только 1 исток и 1 сток. Для приведения к требуемому виду добавляем фиктивный сток. (Сij, Cji) – текущая или остаточная пропускная способность. Шаг 1: Для всех ребер пложим остаточную пропускную способность равной первоначальной пропускной способности. Шаг2: Определяем множество Si, как множество узлов j, в который можно будет перейти из узла i по ребру с положительной остаточной пропускной способностью, т. е. Cij>0 . Если Si ≠ Ø, то выполняем ш3, иначе переходим к ш 4)Шаг 3: на Si выбираем k:Cik=max{Cij} Если k=n, то сквозной путь найден, переходим к ш5, иначе присваиваем i=k и переходим к ш 2)Шаг 4: (откат назад)Если i=1, то сквозной путь невозможен, то находим узел с номером r, непосредственно из списка доступных узлов узла R. Шаг 5: (Определение остаточной сети)Np={1,k1,k2,…,n} исток стокNp – множество узлов, входящих в p-й сквозной путь от истока к стоку n. Тогда максимальный поток, проходящий по этому пути определяется: Остаточные пропускные способности ребер, составляющих сквозной путь уменьшаются на величину fp в направлении движения потока и увеличения на эту же величину в обратном направлении. Шаг 6: РешениеПри m найденных сквозных путях макс поток определяется следующим образом:Оптимальный поток через ребро (i,j) определяется:а) m б)