Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину
Версия от 23:43, 21 декабря 2010; Воронов Филипп (обсуждение | вклад)
Алгоритм Форда — Фалкерсона — алгоритм, решающий задачу нахождения максимального потока в транспортной сети.
Идея
Идея алгоритма заключается в следующем. Изначально величине потока присваивается значение 0: обхода в глубину (dfs). Процесс повторяется, пока можно найти увеличивающий путь.
для всех из . Затем величина потока итеративно увеличивается посредством поиска увеличивающего пути (путь от источника s к стоку t, вдоль которого можно послать больший поток). В данной статье рассматривается алгоритм, осуществляющий этот поиск с помощьюРеализация
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 дельта } }