| Меню | Описание | Сложность | Листинг | Пример |
| |||||||
|
|
Алгоритм Форда-ФалкерсонаАлгоритм Форда-Фалкерсона — решает задачу нахождения максимального потока в транспортной сети. Задача о максимальном потоке для данной сети состоит в следующем: найти максимально возможную скорость производства (и потребления) вещества, при которой его еще можно доставить от истока к стоку при данных пропускных способностях труб. Ключевую роль в методе Форда-Фалкерсона играют два понятия: остаточные сети и дополняющие пути. Пусть дана сеть и поток в ней. Тогда остаточная сеть состоит из тех ребер (называемых также остаточными), поток по которым можно увеличить. Заметим, что остаточное ребро не обязано быть ребром исходной сети. Такие "странные" ребра появляются когда имеется поток вещества в обратном направлении — ведь этот поток можно уменьшить. Назовем дополняющим путем простой путь из истока в сток в остаточной сети. Из определения остаточной сети вытекает, что по всем ребрам дополняющего пути можно переслать ещё сколько-то вещества, не превысив их пропускную способность. Величину наибольшего потока, который можно переслать по дополняющему пути назовем остаточной пропускной способностью пути. Очевидно, она равна значению минимального остаточного ребра, входящего в данный путь. При выполнении каждой итерации метода Форда-Фалкерсона мы находим некоторый увеличивающий путь р, и поток f вдоль каждого ребра данного пути
увеличивается на величину остаточной пропускной способности сf (р). Реализация данного метода вычисляет максимальный поток в графе
G = (V, Е) путем обновления потока f[u,v] между каждой парой вершин и
и v, соединенных ребром. Если вершины u и v не связаны ребром ни в одном направлении, неявно предполагается, что f[u, v] = 0. Предполагается, что значения пропускных способностей задаются вместе с графом и с (u, v) = 0, если (u, v) є Е. Формальное описание [вверх]
Ford_Fulkerson(G, s, t)
1 for (для) каждого ребра (u, v) є E[G]
2 do f[u,v] «-0
3 f[v,u] «- 0
4 while существует путь p из s в t в остаточной сети Gf
5 do сf(р) «— min {cf(u, v) : (u, v) принадлежит р}
6 for (для) каждого ребра (u, v) in p
7 do f[u,v] «- f[u] + cf(p)
8 f[v,u] «- -f[u,v]
Строки 1-3 инициализируют поток f значением 0. В цикле while в строках 4-8 выполняется неоднократный поиск увеличивающего пути р в Gf, и поток f вдоль пути р увеличивается на остаточную пропускную способность Cf (р). Когда увеличивающих путей больше нет, поток f является максимальным. Оценка сложности [вверх]Время выполнения процедуры Ford_Fulkerson зависит от того, как именно выполняется поиск увеличивающего пути р в строке 4. При неудачном методе поиска алгоритм может даже не завершиться: величина потока будет последовательно увеличиваться, но она не обязательно сходится к максимальному значению потока. Выполнение строк 1-3 занимает время в (Е). Цикл while в строках 4-8 выполняется не более |f*| раз, поскольку величина потока за каждую итерацию увеличивается по крайней мере на одну единицу. Время поиска пути в остаточной сети составляет О (V + Е') = О (Е), если используется поиск в глубину или поиск в ширину. Каждая итерация цикла while занимает время О (Е), так что в результате общее время выполнения составляет О(Е|f*|), где f* — максимальный поток, найденный данным алгоритмом. Пример [вверх]Визуализатор алгоритма:Работа базового алгоритма Форда-Фалкерсона (последовательные итерации цикла while). В левой части каждого рисунка показана остаточная сеть Gf с выделенным увеличивающим путем р; в правой части показан новый поток f, который получается в результате прибавления fр к f
|
