37
правок
Изменения
Нет описания правки
== Идея ==
Идея алгоритма заключается в следующем. Изначально величине потока присваивается значение 0: <tex> f(u,v) = 0 </tex> для всех <tex> u, v </tex> из <tex> V </tex>. Затем величина потока итеративно увеличивается посредством поиска увеличивающего пути (путь от источника s к стоку t, вдоль которого можно послать больший поток). В данной статье рассматривается алгоритм, осуществляющий этот поиск с помощью [[Обход в глубину, цвета вершин|обхода в глубину (dfs)]]. Процесс повторяется, пока можно найти увеличивающий путь.
== Реализация ==
dfs(u, Cmin) {
if (u = t)
return Cmin
u.vis <- true
for (uv \in E)
if (!v.vis) && (uv.f < uv.c)
дельта <- dfs(v, min(Cmin, uv.c - uv.f))
if (дельта > 0) {
uv.f += дельта
uv.r.f -= дельта
return дельта
}
}
== См. также ==
* [[Теорема Форда-Фалкерсона]]
