Перебор сквозных путей от истока к стоку с вычислением пропускных способностей этих путей.Для работы алгоритма требуется чтобы в структуре сети были только 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 б)