Алгоритм Форда-Фалкерсона (отыскания 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.