Изменения
→Подробное описание
После этого приступим к построению [[Блокирующий поток|блокирующего потока]]. Пусть вершина <tex>v</tex> принадлежит <tex>k</tex>-ому слою и <tex>p(v)=min (p(w), w \in L_k)</tex>, где <tex>L_k</tex> — <tex>k</tex>-й слой. Протолкнем <tex>p(v)</tex> единиц потока из вершины <tex>v</tex> в смежные с ней вершины по исходящим дугам с [[Дополняющая сеть, дополняющий путь | остаточной пропускной способностью]] <tex>c_f \ne 0</tex>. Попутно будем переносить проталкиваемый поток в исходную сеть, а также корректировать потенциалы вершин, отправляющих и принимающих избыток потока. В результате, весь (в виду минимальности потенциала вершины <tex>v</tex>) проталкиваемый поток соберется в вершинах <tex>(k+1)</tex>-го слоя.
Повторим процесс отправки потока из вершин <tex>(k+1)</tex>-го слоя, содержащих избыток потока, в смежные им вершины <tex>(k+2)</tex>-го слоя. И так до тех пор, пока весь поток не соберется в последнем слое, в котором содержится только сток <tex>t</tex>, ибо все остальные вершины, ранее ему принадлежащие, были удалены, поскольку их потенциалы нулевые. Следовательно, весь поток величины <tex>p(v)</tex>, отправленный из вершины <tex>v</tex>, где <tex>p(v)</tex> - минимальный полностью соберется в <tex>t</tex>. На втором этапе вновь, начиная с вершины <tex>v</tex>, осуществляется подвод потока уже по входящим дугам. В результате на первом шаге недостаток потока переадресуется к узлам <tex>(k-1)</tex>-го слоя, затем <tex>(k-2)</tex>-го. И так до тех пор, пока весь потока величины <tex>p(v)</tex>, отправленные из вершины с минимальным потенциалом<tex>v</tex>, где <tex>p(v)</tex> - минимальный, не соберется в истоке<tex>s</tex>. Таким образом, поток и во вспомогательной и в основной сети увеличится на величину <tex>p</tex>.
