Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину

Алгоритм Форда — Фалкерсона — алгоритм, решающий задачу нахождения максимального потока в транспортной сети.

Идея

Идея алгоритма заключается в следующем. Изначально величине потока присваивается значение 0: [math] f(u,v) = 0 [/math] для всех [math] u, v [/math] из [math] V [/math]. Затем величина потока итеративно увеличивается посредством поиска увеличивающего пути (путь от источника 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 дельта
           }
}

См. также

• Теорема Форда-Фалкерсона