На этом шаге рассмотрим анализ метода Форда-Фалкерсона.
Представим на рисунках пошаговое выполнение алгоритма Форда-Фалкерсона. На рис. 1 представлены последовательные итерации цикла while, слева в каждой части показана остаточная сеть Gf из строки 3 алгоритма с выделенным увеличивающим путем p, справа показан новый поток f, который является результатом увеличения f на fp.
Рис.1. Работа базового алгоритма Форда-Фалкерсона
Строки 1 и 2 алгоритма инициируют поток f значением 0.
1 for каждого ребра (u, v) ∈ G.E
2 (u, v).f = 0
В цикле while в строках 3 - 8 выполняется неоднократный поиск увеличивающего пути p в Gf и увеличение потока f вдоль пути p увеличивается на остаточную пропускную способность cf(p). Каждое остаточное ребро в пути p является либо ребром исходной сети, либо обратным к ребру в исходной сети. В строках 6 - 8 выполняется обновление потока, соответствующее каждому случаю, путем добавления потока, если остаточное ребро является ребром исходной сети, и вычитания в противном случае. Когда увеличивающих путей больше нет, поток f является максимальным.
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)
Время выполнения процедуры Ford-Fulkerson зависит от того, как именно выпоняется поиск увеличивающего пути p в строке 3. При неудачном выборе поиска алгоритм может даже не завершиться: величина потока будет последовательно увеличиваться, но она не обязательно будет сходиться к максимальному значению потока.
Если увеличивающий путь выбирается с использованием поиска в ширину, алгоритм выполняется за полиномиальнное время.
На следующем шаге рассмотрим программный код, реализующий метод Фода-Фалкерсона для решения олимпиадной задачи.
