На этом шаге рассмотрим базовый алгоритм Форда-Фалкерсона.
При выполнении каждой итерации метода Форда-Фалкерсона мы находим некоторый увеличивающий путь p и используем его для того, чтобы изменять поток f.
Вычислим максимальный поток в транспортной сети G = (V, E) путем обновления атрибута потока для каждого ребра (u, v) ∈ E. Если (u, v) ∉ E, неявно предполагается, что f(u, v) = 0. Мы так же считаем, что вместе с транспортной сетью задаются пропускные способности c(u, v), и что c(u, v) = 0, если (u, v) ∉ E. Остаточная пропускная способность cf(u, v) вычисляется по формуле
Выражение cf(p) в коде процедуры является временной переменной, в которой хранится остаточная прпускная способнсть пути p.
Ford-Fulkerson(G, s, t)
1 for каждого ребра (u, v) ∈ G.E
2 (u, v).f = 0
3 while существует путь p из s в t в остаточной сети Gf
4 cf(p) = min{cf(u, v): (u, v) ∈ p}
5 for каждого ребра (u, v) в p
6 if (u, v) ∈ E
7 (u, v).f = (u, v).f + cf(p)
8 else (v, u).f = (v, u).f - cf(p)
Представим атрибут f для ребра (u, v) с помощью того же стиля обозначений - (u, v).f, - что и в случае атрибутов любого другого объекта.
Процедура Ford-Fulkerson является расширением приведенного ранее псевдокода Ford-Fulkerson-Method.
На следующем шаге рассмотрим анализ метода Форда-Фалкерсона.
