Алгоритм нахождения максимального потока.

Идея данного алгоритма состоит в поиске сквозных путей с положительными потоками от источника к стоку.

Рассмотрим ребро (i, j) с (начальной) пропускной способностью .В процессе выполнения алгоритма части этих пропускных способностей "забираются" потоками, проходящими через данное ребро, в результате каждое ребро будет иметь остаточную пропускную способность. Будем использовать запись для представления остаточных пропускных способностей. Сеть, в которой все ребра имеют остаточную пропускную способность, назовем остаточной.

Для произвольного узла j, получающего поток от узла i, определим метку [а_j, i], где a_j— величина потока, протекающего от узла j к узлу i. Чтобы найти максимальный поток, выполним следующие действия:

Этап 1. Для всех ребер (i, j) положим остаточную пропускную способность равной первоначальной пропускной способности, т.е. приравняем . Назначим а₁ = ∞ и пометим узел 1 меткой [∞, —]. Полагаем i = 1 и переходим ко второму этапу.

Этап 2. Определяем множество S, как множество узлов j, в которые можно перейти из узла i по ребру с положительной остаточной пропускной способностью (т.е. с_ij > 0 для всех j? S_i). Если S_i ≠ Ø, выполняем третий этап, в противном случае переходим к п. 4.

Этап 3. Вo множестве S_i находим узел k, такой, что

Положим а_k = с_iк и пометим узел k меткой [а_k, i]. Если последней меткой помечен узел стока (т.е. если k = n), сквозной путь найден, и мы переходим к пятому этапу. В противном случае полагаем i = k и возвращаемся к п. 2.

Этап 4. Откат назад. Если i = 1, сквозной путь невозможен, и мы переходим к п. 6. Если i ≠ l, находим помеченный узел г, непосредственно предшествующий узлу i, и удаляем узел i из множества узлов, смежных с узлом г. Полагаем i = г и возвращаемся ко второму этапу.

Этап 5. Определение остаточной сети. Обозначим через N_p = {1, k₁, k₂,..., n} множество узлов, через которые проходит р-й найденный сквозной путь от узла источника (узел 1) до узла стока (узел n). Тогда максимальный поток, проходящий по этому пути, вычисляется как

Остаточные пропускные способности ребер, составляющих сквозной путь, уменьшаются на величину f_p в направлении движения потока и увеличиваются на эту же величину в противоположном направлении. Таким образом, для ребра (i, j), входящего в сквозной путь, текущие остаточные пропускные способности (c_ij, с_ji.) изменятся следующим образом:

Далее восстанавливаем все узлы, удаленные в п. 4. Полагаем i =1 и возвращаемся ко второму этапу для поиска нового сквозного пути.

Этап 6. Решение.

а). При m найденных сквозных путях максимальный поток вычисляется по формуле

b). Имея значения начальных и конечных пропускных способностей ребра (i, j), можно вычислить оптимальный поток через это ребро следующим образом. Положим . Если α > 0, поток, проходящий через ребро (i, j), равен α. Если же β > 0, тогда поток равен β. (Случай, когда одновременно α > 0 и β > 0, невозможен.)

Процесс отката назад на четвертом этапе выполняется тогда, когда алгоритм должен "убить" промежуточный узел до момента реализации сквозного пути. Коррекцию пропускных способностей, выполняемых в п. 5, можно пояснить на примере простой сети, показанной на рис. 6.30. На рис. 6.30, а найден первый сквозной путь N₁ ={1, 2, 3, 4} с максимальным потоком f₂ = 5. После этого остаточные пропускные способности ребер (1, 2), (2, 3) и (3, 4) изменятся соответственно с (5, 0) на (0, 5). На рис. 6.30, б показан второй сквозной путь N₂ = {1, 3, 2, 4} с максимальным потоком f₂ = 5. После коррекции пропускных способностей получаем сеть, показанную на рис. 6.30, в, где уже невозможно построить сквозной путь. Почему так получилось? При вычислении остаточных пропускных способностей в п. 5 при переходе от сети б к сети в невозможна организация потока в направлении 2 → 3. Получается, что алгоритм как бы «помнит», что поток в направлении 2 —> 3 уже был в предыдущих сквозных путях, и поэтому снова (на пятом этапе) изменяет пропускную способность с 0 до 5 в направлении от узла 3 к узлу 2.

Пример:

Найдем максимальный поток в сети из предыдущего примера (рис. 6.29). На рис. 6.31 предлагается графическая иллюстрация выполнения алгоритма. Считаем полезным сравнить описание выполняемых алгоритмом вычислительных итераций с их графическим представлением.

Итерация 1: Положим остаточные пропускные способности всех ребер равными первоначальным пропускным способностям .

Шаг 1. Назначаем a₁ = ∞ и помечаем узел 1 меткой [∞, —]. Полагаем i = 1.

Шаг 2.

Шаг 3. k = 3, поскольку c_l3= max{c₁₂, с₁₃, с₁₄) = mах{20, 30, 10} = 30. Назначаем а₃ = с₁₃ = 30 и помечаем узел 3 меткой [30, 1]. Полагаем i= 3 и возвращаемся к шагу 2.

Шаг 4. S₂ ={4, 5}.

Шаг 5. k = 5 и а₅ = с₃₅ = mах{10, 20} = 20. Помечаем узел 5 меткой [20, 3]. Получен сквозной путь. Переходим к шагу 5.

Шаг 6. Сквозной путь определяем по меткам, начиная с узла 5 и заканчивая узлом 1: (5) →[20, 3] →(3) → [30, 1] → (1). Таким образом, N₁ = {1, 3, 5} и f₁= min{a₁, а₃, а₅) = {∞, 30, 20} = 20. Вычисляем остаточные пропускные способности вдоль пути N_1.

Итерация 2:

Шаг 1. Назначаем а₁ =∞ и помечаем узел 1 меткой [∞, —]. Полагаем i= 1.

Шаг 2. S₁ = {2, 3, 4}.

Шаг 3. k =2, назначаем а₂ = с₁₂ = mах{20, 10, 10} = 20 и помечаем узел 2 меткой [20, 1]. Полагаем i= 2 и возвращаемся к шагу 2.

 

Шаг 2. S₂ = {3, 5}.

Шаг 3. k =3 и а₃ = с₂₃ = 40. Помечаем узел 3 меткой [40, 2]. Полагаем i = 3 и возвращаемся к шагу 2.

Шаг 2. S₃ = {4} (отметим, что с₃₅ = 0, поэтому узел 5 не включается в S₃).

Шаг 3. k = 4, назначаем а₄= с₃₄ = 10 и помечаем узел 4 меткой [10, 3]. Полагаем i = 4 и возвращаемся к шагу 2.

 

Шаг 2. S₄= {5} (поскольку узлы 1 и 3 уже помечены, они не включаются в 54). k — 5 и аь = с45 = 20. Помечаем сквозной путь. Переходим к шагу 5.

Шаг 3. k = 5 и а₅ = с₄₅ = 20. Помечаем узел 5 меткой [20, 4]. Получен сквозной путь. Переходим к шагу 5.

Шаг 5. N₂ = {1, 2, 3, 4, 5} и f₂ = min{∞, 20, 40,10, 20} = 10. Вычисляем остаточные пропускные способности вдоль пути N₂:

(с₁₂, с₂₁) = (20 - 10, 0 + 10) = (10,10),

(с₂₃, с₃₂) = (40 - 10, 0 + 10) = (30, 10),

(с₃₄, с₄₃) = (10 - 10, 5 + 10) = (0, 15),

(с₄₅, с₅₄) = (20 - 10, 0 + 10) = (10, 10).

Итерация 3:

Шаг 1. Назначаем а₁ = ∞ и помечаем узел 1 меткой [∞, —]. Полагаем i = 1.

Шаг 2. S₁= {2, 3, 4}.

Шаг 3. k = 2, назначаем а₂ = c_l2 = max{10, 10, 10} = 10 и помечаем узел 2 меткой [10, 1]. Полагаем i = 2 и возвращаемся к шагу 2.

 

Шаг 2. S₂={3, 5}.

Шаг 3. k=3 и a₃ = с₂₃= 30. Помечаем узел 3 меткой [30, 2]. Полагаем i = 3 и возвращаемся к шагу 2.

Шаг 2. S₃ = Ø (поскольку с₃₄ = с₃₅ = 0). Переходим к шагу 4.

Шаг 4. Метка [30, 2] узла 3 показывает номер предшествующего узла r = 2. На этой итерации узел 3 в дальнейшем во внимание не принимается, его метку вычеркиваем. Полагаем i = r = 2 и возвращаемся к шагу 2.

 

Шаг 2. S₄={5} (Поскольку узел 3 удален из возможного сквозного пути).

Шаг 3. k=5 и а₅=с₂₅=30. Помечен узел 5 меткой [30,2]. Получен сквозной путь. Переходим к шагу 5.

 

Шаг 5. N₃ = {1, 2, 5} f₃ = min{∞, 10, 30} = 10. Вычисляем остаточные пропускные способности вдоль пути N₃:

(с₁₂, с₂₁) = (10 - 10, 10 + 10) = (0, 20),

(c₂₅, с₅₂) = (30 - 10, 0 + 10) =(20, 10).

Итерация 4. На этой итерации получен путь N₄ = {1, 3, 2, 5} сf₄ = 10.

Итерация 5. На этой итерации получен путь N₅ ={1, 4, 5} сf₅ =10.

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

Шаг 6. Максимальный объем потока в сети равен F =f₁ +f₂ +... +f₅ = 20 + 10 + 10 4- 10 + 10 = 60 единиц. Значения потоков по различным ребрам вычисляются путем вычитания последних значений остаточных пропускных способностей из первоначальных значений пропускных способностей .Результаты вычислений приведены в следующей таблице.

 

 

Тема 12. Нахождение потока наименьшей стоимости

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