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

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

Идея

Идея алгоритма заключается в следующем. Изначально величине потока присваивается значение 0: [math] f(u,v) = 0 [/math] для всех [math] u, v [/math] из [math] V [/math]. Затем величина потока итеративно увеличивается посредством поиска увеличивающего пути (путь от источника s к стоку t, вдоль которого можно послать больший поток). Процесс повторяется, пока можно найти увеличивающий путь.

См. также

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