Алгоритм Форда - Фалкерсона

 

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

Идея алгоритма

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

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

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

Важной частью алгоритма является этап расстановки меток. Каждая вершина может находиться в одном из трех состояний:

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

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

· вершина.

· не помечена;

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

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

 

Описание алгоритма

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

· матрица пропускных способностей дуг

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

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

Шаг 0. Инициализация.

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

Шаг 1. Назначить вершине метку .

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

Шаг 2. Просмотр помеченных вершин.

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

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

.

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

.

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

Шаг 3. Проверка.

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

· если помечена вершина , то на Шаг 4;

· если помечена любая другая вершина, то на Шаг 2.

Если на Шаге 2 нельзя назначить никаких меток, то алгоритм заканчивает работу с некоторым максимальным потоком.