Шаг 4. Обновить поток 
и возвращаться к шагу 2 до тех пор, пока все активные циклы не будут дезактивированы и больше не будет существовать никаких активных циклов; после чего перейти к шагу 5. (На этом этапе поток 
будет оптимальным потоком 
Шаг 5. Найти аугментальный маршрут от 
с наибольшим выигрышем. Посылать поток по этому маршруту до тех пор, пока инкрементальная пропускная способность не уменьшится до нуля.
Шаг 6. Обновить поток 
и повторять шаг 5 до тех пор, пока или чистый выходной поток 
не примет требуемое значение (оптимального потока), или больше не будет существовать никаких аугментальных маршрутов; тогда полученный поток будет оптимально-максимальным потоком 
Шаги вышеприведенного алгоритма очень просты, а сам метод эффективен. Шаги 2 и 5 можно выполнять и с помощью алгцритма кратчайшей цепи. А именно определим инкрементальный граф 
соответствующий графу 
с множеством вершин 
и множеством дуг 
таким, что
причем инкрементальная «стоимость
и пропускная способность
и
инкрементальная «стоимость»
и пропускная способность
Цикл 
в графе 
имеющий выигрыш, больший чем единица, соответствует тогда циклу с отрицательной «стоимостью» в графе 
В этом можно убедиться, прологарифмировав обе части соотношения (11.15), в котором в качестве маршрута 
надо взять цикл 
Тогда получим
где 
как и прежде, — множества прямых и обратных дуг цикла 
Если 
то 
откуда следует, что стоимость цикла 
в 
т. е. 
Должна быть отрицательной. Обратно, если 
то стоимость цикла 
неотрицательна.
Таким образом, активные циклы в 
на шаге 2 вышеописанного алгоритма — могут быть определены посредством нахождения всех кратчайших (наименьшей «стоимости») цепей, идущих из вершин графа 
к конечной вершине 
(для чего можно воспользоваться методом из разд. 2.2.1 гл. 8, как это было объяснено в разд. 4 настоящей главы), и проверки циклов на отрицательную стоимость. Если, однако, поток 
циркулирующий по активному циклу 
на шаге 3 и передаваемый по аугментальному маршруту к 
не уменьшает до нуля пропускную способность самого цикла 
а вместо этого уменьшает до нуля пропускную способность аугментального маршрута, то при следующем выполнении шага 2 нужно только найти другой аугментальный маршрут, ведущий из вершины цикла 
в вершину 
Такой маршрут снова сделает цикл активным и можно будет перейти к шагу 3 и т. д. вплоть до того момента, когда цикл 
дезактивируется. Тогда на шаге 2 ищется некоторый другой активный цикл.
Шаг 5 вышеописанного алгоритма также можно выполнить с помощью метода разд. 2.2.1 гл. 8, так как он состоит просто в вычислении кратчайшей цепи от 
в графе 
Этот граф «освобождается» от циклов отрицательной стоимости, как только выполнены четыре предыдущие шага алгоритма.
(допустим, например, нулевой по каждой дуге поток).
активный цикл 
по отношению к 
такая вершина в 
что аугментальный маршрут начинается в 
и кончается в 
(Заметим, что 
может совпадать с 
Начиная с вершины 
устроить циркуляцию потока 
по активному циклу и передать избыток потока из 
по аугментальному маршруту. Выбрать 
так, чтобы (вместе с существующим потоком В) инкрементальная пропускная способность цикла или аугментального маршрута уменьшилась до нуля.
