Алгоритм Форда-Фалкерсона (отыскания max потока)

1. Пусть j( l)>0, "lÎА; m₀(l)=0; k=1.

2. Находим произвольный ориентированный путь из S^/ в S^// в графе G=(V_k,A_k,j_k) и строим m_k: А® R₊ по следующему правилу.

Выбираем число и строим поток, пропущенный на данной итерации по дугам выбранного пути:

После чего пересчитываем оставшиеся пропускные способности дуг:

3. Дуги, для которых j_к+1( )=Æ, удаляются из G_к+1=(V,A_k+1,j_k+1).

4. Если на шаге k в графе G нельзя найти ориентированный путь из S^/ в S^//, то остановка. Таким образом, m_к( )- искомый поток, а

Иначе, переходим к шагу 2.