Алгоритм форда — фалкерсона — История в новостях.

Разглядим метод Форда-Фалкерсона для фиксированной конфигурации сети.

Мысль метода

Метод начинает работу с начального допустимого потока (быть может, нулевого). После этого осуществляются попытки расширить величину потока посредством систематического поиска всех вероятных цепей из s в t, на которых возможно расширить величину потока (дополняющие цепи).

Поиск дополняющих цепей производится методом расстановки меток, каковые показывают, на каких дугах и на какое количество возможно расширить поток. В то время, когда отыскана одна из таких цепей, поток на протяжении нее возрастает. По окончании чего все метки стираются, и снова полученный поток употребляется в качестве исходного при новой расстановке меток.

Метод заканчивает работу, в то время, когда нельзя найти ни одну дополняющую цепь. Последний отысканный поток есть большим.

Неотъемлемой частью метода есть этап расстановки меток. Любая вершина может пребывать в одном из трех состояний:

вершина помечена и просмотрена (т.е. вершина имеет метку и все смежные с ней вершины «обработаны»);
вершина помечена, но не просмотрена (т.е. вершина имеет метку, но смежные с ней вершины не «обработаны»);
вершина.
не помечена;

pМетка некоей вершиныимеет вид. Часть меткиозначает, что поток возможно увеличен на протяжении дуги. Часть меткиозначает, что поток возможно уменьшен на протяжении дуги. В обоих случаяхпоказывает большую величину, на которую возможно расширить поток отквдоль дополняющей цепи.

Сперва все вершины не имеют меток.

Описание метода

Входными данными метода являются:

матрица пропускных свойств дуг
начальный поток, задаваемый матрицей потоков дуг

При завершении работы метод выдает отысканный большой поток, что определяется матрицей потоков дуг.

Ход 0.Инициализация.

Положим все дуговые потоки равными нулю:.

Ход 1.Назначить вершинеметку.

Сейчас вершинапомечена, но не просмотрена. Все остальные вершины не помечены.

Ход 2.Просмотр помеченных вершин.

Выбрать некую помеченную, но не просмотренную вершину; пускай ее метка будет.

1. Каждой непомеченной вершине, для которой, назначить метку, где

2. Каждой непомеченной вершине, для которойназначить метку, где

Сейчас вершинапомечена и просмотрена, а вершина, метка которой назначена в пунктах 1 либо 2, помечена, но не просмотрена. Каким-либо образом отмечается, что вершинапросмотрена.

Ход 3. Проверка.

В случае если на Шаге 2 какая-либо вершина помечена, то: