информационно-новостной портал
Главная / Статьи / Информатика / Программирование /

Алгоритм Л. Форда - Д. Фалкерсона (1954 г.)

1. Построить произвольный поток j  в сети <G; c> (можно и нулевой).

2. Построить полный поток. Если поток j не полный, то в сети существует путь из v0 в vn, все дуги которого не насыщены. Увеличивая потоки через все дуги такого пути P на величину  получаем путь, некоторая дуга которого является насыщенной. Такую операцию следует повторять до тех пор, пока не получится полный поток.

3. Построить максимальный поток.

А. Начальные пометки. Присвоить источнику пометку 0: l(v1) = 0; а остальным вершинам пометку ¥. Следующий шаг повторять до тех пор, пока в результате его выполнения не будет помечен сток vn либо пока не перестанут появляться новые пометки.

Б. Пересчет пометок. Для каждой помеченной вершины vi, пометить символом +i все непомеченные вершины v (l(v) = ¥), для которых дуги (vi; v) ненасыщенные (т.е. j(vi; v) < c(vi; v)), и символом -i все непомеченные вершины, для которых j(v; vi) > 0.

В. Увеличение потока. Если сток vn не получает новую пометку, то закончить работу алгоритма (максимальный поток найден), в противном случае существует цепь (заметьте: в общем случае - не путь!) v0 ®® vn, все вершины которой помечены. Если ориентация дуги a = (vi; vj) совпадает с направлением прохождения цепи, будем обозначать ее  , в противном случае -  .

Если l(vj) = +i (= (vi; vj)), то положить l(a) = c(a) -j(a). Если l(vj) = -i ( = (vj ; vi)), то положить l(a) = j(a). Пусть  (минимум вычисляется по всем дугам, составляющим указанную цепь). По каждой дуге  поток увеличить на , а по каждой дуге  поток уменьшить на . (При этом величина потока в сети W(j) увеличится на e). Перейти к шагу А.

Просмотров: 694 | Дата добавления: 08.02.2016