Изменения
→Жадный Алгоритм
==Жадный Алгоритм==
Идея заключается в том, чтобы по одному находить пути из [[Определение_сети,_потока|истока ]] <tex>s</tex> в [[Определение_сети,_потока|сток ]] <tex>t</tex>, пока это возможно. [[Обход в глубину, цвета вершин| Обход в глубину]] найдёт все пути из <tex>s</tex> в <tex>t</tex>, если из <tex>s</tex> достижима <tex>t</tex>, а пропускная способность каждого ребра <tex>c(u, v)>0</tex> поэтому, насыщая рёбра, мы хотя бы единожды достигнем стока <tex>t</tex>, следовательно блокирующий поток всегда найдётся.
Используя <tex>dfs</tex> каждый путь находится за <tex>O(E)</tex>, где <tex>E</tex> — число рёбер в графе. Поскольку каждый путь насыщает как минимум одно ребро, всего будет <tex>O(E)</tex> путей. Итого общая асимптотика составляет <tex>O(E^2)</tex>.
