На этом шаге рассмотрим пример применения метода Форда-Фалкерсона для решения задачи о максимальном потоке.
Метод Форда-Фалкерсона назван методом, а не алгоритмом, т.к. он допускает несколько реализаций с различным временем выполнения.
Метод Форда-Фалкерсона базируется на трех идеях, которые используются во многих потоковых алгоритмах и задачах: остаточные сети, увеличивающие пути и разрезы.
Метод Форда-Фалкерсона итеративно увеличивает значение потока. Вначале поток обнуляется: f(u, v) = 0 для всех u, v ∈ V. На каждой итерации величина потоки в G увеличивается посредством поиска "увеличивающего пути" в связанной "остаточной сети" Gf. Зная ребра увеличивающего пути в Gf, мы можем идентифицировать конкретные ребра в G, для которых можно изменить поток таким образом, что его величина увеличится.
Каждая итерация метода Форда-Фалкерсона увеличивает величину потока, но как будет видно далее, поток через конкретное ребро G может возрастать или уменьшаться; уменьшение потока через некоторые ребра может быть необходимым для того, чтобы позволить алгоритму переслать больший поток от истока к стоку. Мы многократно увеличивам поток до тех пор, пока остаточная сеть не будет иметь ни одного увеличивающего пути.
Метод Форда-Фалкерсона можно задать следующей функцией:
Ford-Fulkerson-Method(G, s, t)
1 Инициализация потока f нулевым значением
2 while существует увеличивающий путь p в остаточной сети Gf
3 увеличиваем поток f вдоль пути p
4 return f
В процедуре используются следующие обозначения:
- Транспортная сеть G = (V, E) представляет собой ориентированный граф, в котором каждое ребро (u, v) ∈ E имеет неотрицательную пропускную способность c(u, v) ≥ 0
- Две вершины транспортной сети s - исток и t - сток.
На следующем шаге рассмотрим понятие остаточной сети в методе Форда-Фалкерсона.
