Алгоритм расстановки пометок нахождения увеличивающего пути

Шаг 1. Источник s получает метку (s⁺).

Шаг 2. Для всех дуг (s,j) выходящих из вершины s, соответствующие вершины j получают метку s⁺, если x_{sj } d_sj. Для дуг (i,s), входящих в вершину s, соответствующие вершины i получают метку (s^-), если x_is 0.

Шаг k. Просматриваем все вершины, помеченные на (k-1)- ом шаге. Для каждой такой вершины k, соответствующие им вершины j, для которых x_ki d_kj, получают метку (k⁺), для всех дуг (i,k), входящих в вершину k, соответст­вующих им вершины i , для которых x_ik  0, получают метку (k ^-).

Алгоритм заканчивает работу одним из двух состояний: а) после некото­рого шага мы не можем пометить ни одной вершины, и сток t остался непоме­ченным. Это означает, что имеющийся поток является максимальным, а (R, ), где R –множество помеченных, - множество непомеченных вершин, образует минимальный разрез; б) стокt оказался помеченным. Двигаясь от стока t к вершине, номер которой указан в ее метке и т.д., мы придем к источнику.

Алгоритм Форда – построения максимального потока в сети.

Начальный. Выбираем некоторый поток в сетиG (V,U) (например x_{i j}= 0 для всех дуг (i,j) U).

Общая итерация 1. Применяем алгоритм нахождения увеличивающего пути из источника s в сток t. Если такого пути нет, то построенный поток яв­ляется максимальным. Алгоритм заканчивает работу. Если увеличивающий путь найден, то переходим к 2.

2. В найденном увеличивающем пути обозначим через P⁺ множество прямых, а P ^- - множество обратных дуг пути и вычисляем величину ₁ = (d_ij – x_ij)  0 и _{2 =} . Полагаем q = min (₁, ₂). Увеличиваем поток вдоль пути P на величину , полагая

x_ij^’ = x_ij+ ,если (i ,j)  P⁺

x_ij^’ = x_ij – , если (i, j)  P^- (23)

x_ij^’ = x_ij для остальных дуг пути.

Переходим к 1.

Рассмотрим пример. На рис.1. изображена сеть. Первое число в скобках указывает пропускную способность дуги, второе – дуговой поток.

Рис.1.

Найдем увеличивающий путь.

Общая итерация: Шаг 1. Источник s получает пометку (s⁺).

Шаг 2. Так как = 1 = 2, то вершина 1 получает метку (s⁺). Вер­шина 2 получает метку (s^-), т.к. x₂₁ = 1  0. Вершина 5 не может быть помечена, т.к. (дуга (s, 5) – насыщенная).

Шаг 3. Соседними вершинами с вновь помеченными являются вершины 3 и 4. Вершина 3 помечена не может быть, так как x₁₃ = d₁₃..Вершина 4 получает пометку (2^-), т.к. х₄₂ = 1  0.

Шаг 4. Соседними с помеченной вершиной 4 являются вершины t и 5. Вершина t помечена не может быть, т.к. х_t4 = 0. Вершина 5 получает пометку (4^-), т.к. x₅₄=10.

Шаг 5. Помечаем вершину t с меткой (5⁺), x₅₁=1 < d₅₁=3.

Увеличивающий путь: s – 2 – 4 – 5 - t , причем на этом пути дуга (5, t) является прямой, а дуги (2, s); (4, 2); (5, 4) обратными.

Увеличим поток вдоль этого пути по формулам (23).

Находим

 ₁

 ₂ =

т.е.  = min( ₁, ₂) = 1.

Полагаем

_2S = x_2S – 1 = 0, ₄₂ = x₄₂ –1 =0, ₅₄ = x₅₄ – 1 = 0, _5t = x_{5 t}+1 = 2.

Величина суммарного потока в сети равна 3.

Общая итерация 1. Для нового потока ищем увеличивающий путь мето­дом расстановки пометок. Пометить удается только вершины s и 1. Следова­тельно, увеличивающего пути нет, и построенный поток является максималь­ным. Минимальный разрез (R,, , где R = 1; 2, = 2; 3; 4; 5; t состоит из дуг (R, ) = (1, 3); (s, 5); (s,2); (1,2) и обладает пропускной способностью

C (R, ) = d₁₃ + d_S5 = 3.

На рис.2 минимальный разрез показан пунктирной линией

Рис. 2