Алгоритм максимального потока Push-Relabel

Алгоритм в математической оптимизации

В математической оптимизации алгоритм push–relabel (альтернативно, preflow–push algorithm ) — это алгоритм для вычисления максимальных потоков в потоковой сети . Название «push–relabel» происходит от двух основных операций, используемых в алгоритме. На протяжении всего выполнения алгоритм поддерживает «предпоток» и постепенно преобразует его в максимальный поток, перемещая поток локально между соседними узлами с помощью операций push под руководством допустимой сети, поддерживаемой операциями relabel . Для сравнения, алгоритм Форда–Фалкерсона выполняет глобальные дополнения, которые отправляют поток по путям от источника до стока. ^[1]

Алгоритм push-relabel считается одним из самых эффективных алгоритмов максимального потока. Общий алгоритм имеет сильно полиномиальную временную сложность O ( V  ² E ) , которая асимптотически более эффективна, чем алгоритм Эдмондса–Карпа O ( VE  ² ) . ^[2] Конкретные варианты алгоритмов достигают еще более низкой временной сложности. Вариант, основанный на правиле выбора узла с наивысшей меткой, имеет временную сложность O ( V  ² √ E ) и обычно рассматривается как эталон для алгоритмов максимального потока. ^{[3] [4]} Субкубическая временная сложность O ( VE log( V  ² / E )) может быть достигнута с помощью динамических деревьев , хотя на практике это менее эффективно. ^[2]

Алгоритм push-relabel был расширен для вычисления потоков с минимальной стоимостью . ^[5] Идея меток расстояний привела к более эффективному алгоритму увеличивающегося пути, который, в свою очередь, может быть включен обратно в алгоритм push-relabel для создания варианта с еще более высокой эмпирической производительностью. ^{[4] [6]}

История

Концепция предпотока была первоначально разработана Александром В. Карзановым и опубликована в 1974 году в «Советских математических докладах» 15. Этот алгоритм предпотока также использовал операцию проталкивания; однако он использовал расстояния во вспомогательной сети для определения того, куда проталкивать поток, вместо системы маркировки. ^{[2] [7]}

Алгоритм push-relabel был разработан Эндрю В. Голдбергом и Робертом Тарьяном . Алгоритм был первоначально представлен в ноябре 1986 года в STOC '86: Proceedings of the eighteenth annual ACM symposium on Theory of computing, а затем официально в октябре 1988 года в качестве статьи в Journal of the ACM. Обе статьи подробно описывают общую форму алгоритма, завершающуюся за O ( V  ² E ), вместе с последовательной реализацией O ( V  ³ ) , реализацией O ( VE  log( V  ² / E )) с использованием динамических деревьев и параллельной/распределенной реализацией. ^{[2] [8]} Как поясняется в ^[9] , Голдберг-Тарьян ввел метки расстояний, включив их в параллельный алгоритм максимального потока Йосси Шилоаха и Узи Вишкина . ^[10]

Концепции

Определения и обозначения

Позволять:

• G = ( V , E ) — сеть с функцией пропускной способности c : V × V → _∞ ${\displaystyle \mathbb {R} }$ ,
• F = ( G , c , s , t ) — сеть потоков , где s ∈ V и t ∈ V — выбранные вершины источника и стока соответственно,
• f  : V × V → ${\displaystyle \mathbb {R} }$ обозначает предпоток в F ,
• x _f  : V → ${\displaystyle \mathbb {R} }$ обозначим избыточную функцию относительно потока f , определяемую как x _f ( u ) = Σ _{v ∈ V} f ( v , u ) − Σ _{v ∈ V} f ( u , v ) ,
• c _f  : V × V → _∞ ${\displaystyle \mathbb {R} }$ обозначает функцию остаточной пропускной способности относительно потока f , определяемую как c _f  ( e ) = c ( e ) − f  ( e ) ,
• E _f ⊂ E — ребра, где f < c ,

и

• G _f ( V , E _f  ) обозначаютостаточную сеть Gотносительно потока f .

Алгоритм push–relabel использует неотрицательную целочисленную допустимую функцию маркировки , которая использует метки расстояний или высоты на узлах для определения того, какие дуги следует выбрать для операции push. Эта функция маркировки обозначается как 𝓁 : V → ${\displaystyle \mathbb {N} }$ . Эта функция должна удовлетворять следующим условиям, чтобы считаться допустимой:

Действительная маркировка :

𝓁( u ) ≤ 𝓁( v ) + 1 для всех ( u , v ) ∈ E _f

Исходное состояние :

𝓁( s ) = |  V  |

Сохранение раковины :

𝓁( т ) = 0

В алгоритме значения меток s и t фиксированы. 𝓁( u ) — нижняя граница невзвешенного расстояния от u до t в G _{f ,}   если t достижим из u . Если u был отключен от t , то 𝓁( u ) − |  V  | — нижняя граница невзвешенного расстояния от u до s . В результате, если существует допустимая функция маркировки, в G _f нет путей s - t ,   поскольку ни один из таких путей не может быть длиннее |  V  | − 1 .

Дуга ( u , v ) ∈ E _f   называется допустимой, если 𝓁( u ) = 𝓁( v ) + 1 . Допустимая сеть G̃ _f ( V , Ẽ _f  ) состоит из множества дуг e ∈ E _f   , которые являются допустимыми. Допустимая сеть ациклична.

Для фиксированного потока f вершина v ∉ { s, t } называется активной , если она имеет положительный избыток относительно f , т. е. x _f ( u ) > 0 .

Операции

Инициализация

Алгоритм начинается с создания остаточного графа, инициализации значений предпотока нулем и выполнения набора насыщающих операций push на остаточных дугах ( s , v ), выходящих из источника, где v ∈ V \ { s } . Аналогично метки инициализируются таким образом, что метка в источнике представляет собой количество узлов в графе, 𝓁( s ) = |  V  | , а всем остальным узлам присваивается метка ноль. После завершения инициализации алгоритм многократно выполняет операции push или relabel над активными узлами до тех пор, пока не будет выполнена ни одна применимая операция.

Толкать

Операция push применяется к допустимой внешней дуге ( u , v ) активного узла u в G _f . Она перемещает min{ x _f ( u ), c _​​f ( u , v )} единиц потока из u в v .

нажимаем (u, v): утверждать x f [u] > 0 и 𝓁[u] == 𝓁[v] + 1 Δ = min(x f [u], c[u][v] - f[u][v]) ф[у][в] += Δ f[v][u] -= Δ х ф [и] -= Δ х f [v] += Δ

Операция push, которая заставляет f  ( u , v ) достичь c ( u , v ) , называется насыщающим push , поскольку она использует всю доступную емкость остаточной дуги. В противном случае весь избыток в узле проталкивается через остаточную дугу. Это называется ненасыщающим push или ненасыщающим push .

Перемаркировать

Операция перемаркировки применяется к активному узлу u, который не является ни источником, ни стоком без каких-либо допустимых исходящих дуг в G _f . Она изменяет 𝓁( u ) на минимальное значение, при котором создается допустимая исходящая дуга. Обратите внимание, что это всегда увеличивает 𝓁( u ) и никогда не создает крутую дугу, которая является дугой ( u , v ) такой, что c _f  ( u , v ) > 0 , и 𝓁( u ) > 𝓁( v ) + 1 .

переименовать(u): утверждают x f [u] > 0 и 𝓁[u] <= 𝓁[v] для всех v таких, что c f [u][v] > 0 𝓁[u] = 1 + min(𝓁[v] для всех v таких, что c f [u][v] > 0)

Эффекты push и relabel

После операции push или relabel 𝓁 остается допустимой функцией маркировки по отношению к f .

Для операции push на допустимой дуге ( u , v ) она может добавить дугу ( v , u ) к E _f , где 𝓁( v ) = 𝓁( u ) − 1 ≤ 𝓁( u ) + 1 ; она также может удалить дугу ( u , v ) из E _f , где она фактически снимает ограничение 𝓁( u ) ≤ 𝓁( v ) + 1 .

Чтобы увидеть, что операция перемаркировки на узле u сохраняет действительность 𝓁( u ) , обратите внимание, что это тривиально гарантируется определением для исходящих дуг u в G _f . Для входящих дуг u в G _f увеличившееся 𝓁( u ) может только менее строго удовлетворять ограничениям, но не нарушать их.

Общий алгоритм push-relabel

Алгоритм generic push–relabel используется только в качестве доказательства концепции и не содержит подробностей реализации о том, как выбрать активный узел для операций push и relabel. Эта общая версия алгоритма завершится за O ( V ² E ) .

Так как 𝓁( s ) = |  V  | , 𝓁( t ) = 0 , и нет путей длиннее |  V  | − 1 в G _f , для того, чтобы 𝓁( s ) удовлетворял допустимому условию маркировки , s должен быть отключен от t . При инициализации алгоритм выполняет это требование, создавая предварительный поток f , который насыщает все исходящие дуги s , после чего 𝓁( v ) = 0 тривиально допустимо для всех v ∈ V \ { s , t } . После инициализации алгоритм многократно выполняет применимую операцию push или relabel до тех пор, пока такие операции не будут применены, после чего предварительный поток преобразуется в максимальный поток.

generic-push-relabel(G, c, s, t): создать предварительный поток f, который насыщает все исходящие дуги s пусть 𝓁[s] = |V| пусть 𝓁[v] = 0 для всех v ∈ V \ {s}, пока есть применимая операция push или relabel do выполнить операцию

Корректность

Алгоритм поддерживает условие, что 𝓁 является допустимой маркировкой во время его выполнения. Это можно доказать, изучив эффекты операций push и relabel на функцию метки 𝓁 . Операция relabel увеличивает значение метки на соответствующий минимум плюс один, который всегда будет удовлетворять ограничению 𝓁( u ) ≤ 𝓁( v ) + 1. Операция push может отправить поток из u в v, если 𝓁( u ) = 𝓁( v ) + 1 . Это может добавить ( v , u ) к G _f  и может удалить ( u , v ) из G _f  . Добавление ( v , u ) к G _f  не повлияет на допустимую маркировку, поскольку 𝓁( v ) = 𝓁( u ) − 1 . Удаление ( u , v ) из Gf  удаляет соответствующее ограничение, поскольку допустимое свойство маркировки 𝓁 ₍ u ) ≤ 𝓁( v ) + 1 применяется только к остаточным дугам в Gf _.  ^[8]

Если существует предпоток f и допустимая маркировка 𝓁 для f , то в остаточном графе G _f нет увеличивающего пути от s до t . Это можно доказать от противного на основе неравенств, которые возникают в функции маркировки при предположении, что увеличивающий путь существует. Если алгоритм завершается, то все узлы в V \ { s , t } неактивны. Это означает, что все v ∈ V \ { s , t } не имеют избыточного потока, и без избытка предпоток f подчиняется ограничению сохранения потока и может считаться нормальным потоком. Этот поток является максимальным потоком согласно теореме о максимальном потоке и минимальном разрезе , поскольку нет увеличивающего пути от s до t . ^[8] 

Таким образом, по завершении работы алгоритм вернет максимальный поток.

Сложность времени

Чтобы ограничить временную сложность алгоритма, мы должны проанализировать количество операций push и relabel, которые происходят в основном цикле. Количество операций relabel, saturating push и nonsaturating push анализируется отдельно.

В алгоритме операция перемаркировки может быть выполнена не более (2|  V  | − 1)(|  V  | − 2) < 2|  V  | ² раз. Это связано с тем, что значение маркировки 𝓁( u ) для любого узла u никогда не может уменьшиться, а максимальное значение метки не более 2|  V  | − 1 для всех узлов. Это означает, что операция перемаркировки потенциально может быть выполнена 2|  V  | − 1 раз для всех узлов V \ { s , t } (т. е. |  V  | − 2 ). Это приводит к ограничению O ( V  ² ) для операции перемаркировки.

Каждый насыщающий push на допустимой дуге ( u , v ) удаляет дугу из G _f  . Чтобы дуга была повторно вставлена ​​в G _f  для другого насыщающего push, v сначала должна быть перемаркирована, затем push на дуге ( v , u ) , затем u должна быть перемаркирована. В процессе 𝓁( u ) увеличивается как минимум на два. Следовательно, существует O ( V ) насыщающих push на ( u , v ) , а общее количество насыщающих push не превышает 2|  V  ||  E  | . Это приводит к временному ограничению O ( VE ) для операций насыщающего push.

Ограничение числа ненасыщающих push может быть достигнуто с помощью потенциального аргумента . Мы используем потенциальную функцию Φ = Σ _{[ u ∈ V ∧ x f  ( u ) > 0]} 𝓁( u ) (т. е. Φ является суммой меток всех активных узлов). Очевидно, что Φ изначально равно 0 и остается неотрицательным на протяжении всего выполнения алгоритма. Как перемаркировка, так и насыщающие push могут увеличить Φ . Однако значение Φ должно быть равно 0 при завершении, поскольку в конце выполнения алгоритма не может остаться никаких активных узлов. Это означает, что в ходе выполнения алгоритма ненасыщающие push-операции должны составлять разницу между операциями relabel и saturative push-операции, чтобы Φ завершилось со значением 0. Операция relabel может увеличить Φ не более чем на (2|  V  | − 1)(|  V  | − 2) . Насыщающий push на ( u , v ) активирует v , если он был неактивен до push-операции, увеличивая Φ не более чем на 2|  V  | − 1 . Следовательно, общий вклад всех операций насыщающих push-операций в Φ не более чем на (2|  V  | − 1)(2|  V  ||  E  |) . Ненасыщающий push на ( u , v ) всегда деактивирует u , но он также может активировать v, как в насыщающем push-операции. В результате он уменьшает Φ по крайней мере на 𝓁( u ) − 𝓁( v ) = 1 . Поскольку перемаркировки и насыщающие push увеличивают Φ , общее количество ненасыщающих push должно составлять разницу (2|  V  | − 1)(|  V  | − 2) + (2|  V  | − 1)(2|  V  ||  E  |) ≤ 4|  V  | ² |  E  | . Это приводит к временному ограничению O ( V  ² E ) для ненасыщающих операций push.

В целом, алгоритм выполняет O ( V  ² ) перемаркировок, O ( VE ) насыщающих push-ов и O ( V  ² E ) ненасыщающих push-ов. Структуры данных могут быть спроектированы для выбора и выполнения соответствующей операции за время O (1) . Таким образом, временная сложность алгоритма составляет O ( V  ² E ) . ^{[1] [8]}

Пример

Ниже приведен пример выполнения универсального алгоритма push-relabel, определенного выше, на следующей простой схеме сетевого потока.

В примере значения h и e обозначают метку 𝓁 и избыток x _f  , соответственно, узла во время выполнения алгоритма. Каждый остаточный граф в примере содержит только остаточные дуги с емкостью больше нуля. Каждый остаточный граф может содержать несколько итераций цикла выполнения операции .

Пример (но с начальным потоком 0) можно запустить здесь в интерактивном режиме.

Практические реализации

В то время как общий алгоритм push–relabel имеет временную сложность O ( V  ² E ) , эффективные реализации достигают O ( V  ³ ) или более низкой временной сложности за счет применения соответствующих правил при выборе применимых операций push и relabel. Эмпирическая производительность может быть дополнительно улучшена с помощью эвристики.

Структура данных «ток-дуга» и операция разряда

Структура данных "current-arc" представляет собой механизм посещения входящих и исходящих соседей узла в потоковой сети в статическом циклическом порядке. Если для узла создается односвязный список соседей, структура данных может быть такой же простой, как указатель на список, который проходит по списку и возвращается к началу, когда он заканчивается.

На основе структуры данных «текущая дуга» можно определить операцию разряда. Операция разряда применяется к активному узлу и многократно выталкивает поток из узла, пока он не станет неактивным, перемаркируя его по мере необходимости для создания допустимых дуг в процессе.

discharge(u): пока x f [u] > 0 do  если текущая дуга[u] вышла за пределы neighbors[u] , то переименовать(u) перемотка тока-дуги[u] иначе  пусть (u, v) = current-arc[u] если (u, v) допустимо , то нажимаем (u, v) пусть current-arc[u] указывает на следующего соседа u

Поиск следующего допустимого ребра для перемещения имеет амортизированную сложность . Указатель текущей дуги перемещается к следующему соседу только тогда, когда ребро к текущему соседу насыщено или недопустимо, и ни одно из этих двух свойств не может измениться, пока активный узел не будет перемаркирован. Таким образом, когда указатель уходит, допустимых ненасыщенных ребер нет, и нам приходится перемаркировать активный узел , поэтому перемещение указателя оплачивается операцией перемаркировки. ^[8] ${\displaystyle O(1)}$ ${\displaystyle u}$ ${\displaystyle u}$ ${\displaystyle O(V)}$ ${\displaystyle O(V)}$

Правила выбора активных узлов

Определение операции разрядки сводит алгоритм push–relabel к многократному выбору активного узла для разрядки. В зависимости от правила выбора алгоритм демонстрирует различную временную сложность. Для краткости мы игнорируем s и t при ссылке на узлы в следующем обсуждении.

Правило выбора FIFO

Алгоритм FIFO push–relabel ^[2] организует активные узлы в очередь. Начальные активные узлы могут быть вставлены в произвольном порядке. Алгоритм всегда удаляет узел в начале очереди для выгрузки. Всякий раз, когда неактивный узел становится активным, он добавляется в конец очереди.

Алгоритм имеет временную сложность O ( V  ³ ) .

Правило выбора «переместить метку вперед»

Алгоритм relabel-to-front push–relabel ^[1] организует все узлы в связанный список и сохраняет инвариант, что список топологически отсортирован относительно допустимой сети. Алгоритм сканирует список от начала до конца и выполняет операцию разрядки на текущем узле, если он активен. Если узел перемаркирован, он перемещается в начало списка, и сканирование перезапускается с начала.

Алгоритм также имеет временную сложность O ( V  ³ ) .

Правило выбора наивысшей метки

Алгоритм push-relabel с наивысшей меткой ^[11] организует все узлы в сегменты, индексированные по их меткам. Алгоритм всегда выбирает активный узел с наибольшей меткой для выгрузки.

Алгоритм имеет временную сложность O ( V  ² √ E ) . Если вместо этого использовать правило выбора наименьшей метки, временная сложность становится O ( V  ² E ) . ^[3]

Методы внедрения

Хотя в описании общего алгоритма push-relabel выше 𝓁( u ) устанавливается равным нулю для каждого узла u, кроме s и t в начале, предпочтительнее выполнить обратный поиск в ширину от t для вычисления точных меток. ^[2]

Алгоритм обычно разделяется на две фазы. Фаза 1 вычисляет максимальный предварительный поток, выгружая только активные узлы, метки которых ниже n . Фаза 2 преобразует максимальный предварительный поток в максимальный поток, возвращая избыточный поток, который не может достичь t , в s . Можно показать, что фаза 2 имеет временную сложность O ( VE ) независимо от порядка операций push и relabel и, следовательно, доминирует над фазой 1. В качестве альтернативы, ее можно реализовать с помощью разложения потока. ^[9]

Эвристики имеют решающее значение для улучшения эмпирической производительности алгоритма. ^[12] Две наиболее часто используемые эвристики — это эвристика пробелов и эвристика глобальной перемаркировки. ^{[2] [13]} Эвристика пробелов обнаруживает пробелы в функции маркировки. Если есть метка 0 < 𝓁 ' < |  V  |, для которой нет узла u такого, что 𝓁( u ) = 𝓁 ' , то любой узел u с 𝓁 ' < 𝓁( u ) < |  V  | был отключен от t и может быть немедленно перемаркирован в (|  V  | + 1) . Эвристика глобальной перемаркировки периодически выполняет обратный поиск в ширину из t в G _f  для вычисления точных меток узлов. Обе эвристики пропускают бесполезные операции перемаркировки, которые являются узким местом алгоритма и способствуют неэффективности динамических деревьев. ^[4]

Примеры реализаций

Реализация на языке С

#include <stdlib.h> #include <stdio.h>  #define УЗЛЫ 6 #define MIN(X,Y) ((X) < (Y) ? (X) : (Y)) #define INFINITE 10000000void push ( const int * const * C , int ** F , int * избыток , int u , int v ) { int send = MIN ( избыток [ u ], C [ u ][ v ] - F [ u ][ v ]); F [ u ][ v ] += отправить ; F [ v ][ u ] -= отправить ; избыток [ u ] -= отправить ; избыток [ v ] += отправить ; }                                   void relabel ( const int * const * C , const int * const * F , int * height , int u ) { int v ; int min_height = INFINITE ; for ( v = 0 ; v < NODES ; v ++ ) { if ( C [ u ][ v ] - F [ u ][ v ] > 0 ) { min_height = MIN ( min_height , height [ v ]); height [ u ] = min_height + 1 ; } } } ;                                                  void discharge ( const int * const * C , int ** F , int * избыток , int * высота , int * видно , int u ) { while ( избыток [ u ] > 0 ) { if ( видно [ u ] < УЗЛЫ ) { int v = видно [ u ]; if (( C [ u ][ v ] - F [ u ][ v ] > 0 ) && ( высота [ u ] > высота [ v ])) { push ( C , F , избыток , u , v ); } else { видно [ u ] += 1 ; } } else { переименовать ( C , F , высота , u ); видно [ u ] = 0 ; } } }                                                                   void moveToFront ( int i , int * A ) { int temp = A [ i ]; int n ; for ( n = i ; n > 0 ; n -- ) { A [ n ] = A [ n -1 ]; } A [ 0 ] = temp ; }                           int pushRelabel ( const int * const * C , int ** F , int source , int sink ) { int * избыток , * высота , * список , * увиденное , i , p ;                      избыток = ( int * ) calloc ( УЗЛЫ , sizeof ( int )); высота = ( int * ) calloc ( УЗЛЫ , sizeof ( int )); видно = ( int * ) calloc ( УЗЛЫ , sizeof ( int ));                  список = ( целое число * ) calloc (( УЗЛЫ -2 ), sizeof ( целое число ));      для ( i = 0 , p = 0 ; i < УЗЛЫ ; i ++ ) { если (( i != источник ) && ( i != приемник )) { список [ p ] = i ; p ++ ; } }                          высота [ источник ] = УЗЛЫ ; избыток [ источник ] = БЕСКОНЕЧНОСТЬ ; для ( i = 0 ; i < УЗЛЫ ; i ++ ) push ( C , F , избыток , источник , i );                   p = 0 ; while ( p < NODES - 2 ) { int u = list [ p ]; int old_height = height [ u ]; discharge ( C , F , extra , height , seen , u ); if ( height [ u ] > old_height ) { moveToFront ( p , list ); p = 0 ; } else { p += 1 ; } } int maxflow = 0 ; for ( i = 0 ; i < NODES ; i ++ ) maxflow += F [ source ][ i ];                                                         бесплатно ( список ); свободный ( видимый ); свободный ( высота ); свободный ( избыток );   вернуть максимальный поток ; } void printMatrix ( const int * const * M ) { int i , j ; for ( i = 0 ; i < УЗЛЫ ; i ++ ) { for ( j = 0 ; j < УЗЛЫ ; j ++ ) printf ( "%d \t " , M [ i ][ j ]); printf ( " \n " ); } }                              int main ( void ) { int ** flow , ** capacitys , i ; flow = ( int ** ) calloc ( NODES , sizeof ( int * )); capacity = ( int ** ) calloc ( NODES , sizeof ( int * )); for ( i = 0 ; i < NODES ; i ++ ) { flow [ i ] = ( int * ) calloc ( NODES , sizeof ( int )); capacity [ i ] = ( int * ) calloc ( NODES , sizeof ( int )); }                                         // Пример графа мощностей [ 0 ][ 1 ] = 2 ; мощностей [ 0 ][ 2 ] = 9 ; мощностей [ 1 ][ 2 ] = 1 ; мощностей [ 1 ][ 3 ] = 0 ; мощностей [ 1 ][ 4 ] = 0 ; мощностей [ 2 ][ 4 ] = 7 ; мощностей [ 3 ][ 5 ] = 7 ; мощностей [ 4 ][ 5 ] = 4 ;                         printf ( "Вместимость: \n " ); printMatrix ( емкости );  printf ( "Максимальный поток: \n %d \n " , pushRelabel ( емкости , поток , 0 , 5 ));     printf ( "Потоки: \n " ); printMatrix ( flow );  вернуть 0 ; } 

Реализация Python

def  relabel_to_front ( C ,  source :  int ,  sink :  int )  ->  int :  n  =  len ( C )  # C - матрица пропускной способности  F  =  [[ 0 ]  *  n  for  _  in  range ( n )]  # остаточная пропускная способность от u до v равна C[u][v] - F[u][v] height  =  [ 0 ]  *  n  # высота узла  избыток  =  [ 0 ]  *  n  # поток в узел минус поток из узла  виден  =  [ 0 ]  *  n  # соседи видны с момента последней перемаркировки  # узел "очередь"  nodelist  =  [ i  for  i  in  range ( n )  if  i  !=  source  and  i  !=  sink ] def  push ( u ,  v ):  send  =  min ( excess [ u ],  C [ u ][ v ]  -  F [ u ][ v ])  F [ u ][ v ]  +=  send  F [ v ][ u ]  -=  send  extra [ u ]  -=  send  extra [ v ]  +=  send def  relabel ( u ):  # Найти наименьшую новую высоту, делающую возможным толчок,  # если такой толчок вообще возможен.  min_height  =  ∞  для  v  в  диапазоне ( n ):  если  C [ u ][ v ]  -  F [ u ][ v ]  >  0 :  min_height  =  min ( min_height ,  height [ v ])  height [ u ]  =  min_height  +  1 def  discharge ( u ):  while  extra [ u ]  >  0 :  if  seen [ u ]  <  n :  # проверить следующего соседа  v  =  seen [ u ]  if  C [ u ][ v ]  -  F [ u ][ v ]  >  0  and  height [ u ]  >  height [ v ]:  push ( u ,  v )  else :  seen [ u ]  +=  1  else :  # мы проверили всех соседей. необходимо перемаркировать  relabel ( u )  seen [ u ]  =  0 height [ source ]  =  n  # самый длинный путь от источника до стока меньше n long  extra [ source ]  =  ∞  # отправить как можно больше потока соседям источника  for  v  in  range ( n ):  push ( source ,  v ) p  =  0  while  p  <  len ( nodelist ):  u  =  nodelist [ p ]  old_height  =  height [ u ]  discharge ( u )  if  height [ u ]  >  old_height :  nodelist . insert ( 0 ,  nodelist . pop ( p ))  # перейти в начало списка  p  =  0  # начать с начала списка  else :  p  +=  1 возврат  суммы ( F [ источник ])

Ссылки

1. Cormen, TH ; Leiserson, CE ; Rivest, RL ; Stein, C. (2001). "§26 Максимальный поток". Введение в алгоритмы (2-е изд.). The MIT Press. стр. 643–698. ISBN 978-0262032933.
2. Голдберг, А. В.; Тарьян, Р. Э. (1986). "Новый подход к проблеме максимального потока". Труды восемнадцатого ежегодного симпозиума ACM по теории вычислений – STOC '86 . стр. 136. doi :10.1145/12130.12144. ISBN 978-0897911931. S2CID  14492800.
3. Ахуджа, Равиндра К.; Кодиалам, Мурали; Мишра, Аджай К.; Орлин, Джеймс Б. (1997). "Вычислительные исследования алгоритмов максимального потока". Европейский журнал операционных исследований . 97 (3): 509. CiteSeerX 10.1.1.297.2945 . doi :10.1016/S0377-2217(96)00269-X. 
4. Goldberg, Andrew V. (2008). "The Partial Augment–Relabel Algorithm for the Maximum Flow Problem". Алгоритмы – ESA 2008 . Lecture Notes in Computer Science. Vol. 5193. pp. 466–477. CiteSeerX 10.1.1.150.5103 . doi :10.1007/978-3-540-87744-8_39. ISBN  978-3-540-87743-1.
5. Голдберг, Эндрю В. (1997). «Эффективная реализация алгоритма масштабирования потока с минимальной стоимостью». Журнал алгоритмов . 22 : 1–29. doi :10.1006/jagm.1995.0805.
6. Ахуджа, Равиндра К.; Орлин, Джеймс Б. (1991). «Алгоритмы пути увеличения, направленные на расстояние, для задач максимального потока и параметрического максимального потока». Naval Research Logistics . 38 (3): 413. CiteSeerX 10.1.1.297.5698 . doi :10.1002/1520-6750(199106)38:3<413::AID-NAV3220380310>3.0.CO;2-J. 
7. Голдберг, Эндрю В.; Тарьян, Роберт Э. (2014). «Эффективные алгоритмы максимального потока». Сообщения ACM . 57 (8): 82. doi :10.1145/2628036. S2CID  17014879.
8. Голдберг, Эндрю В.; Тарьян, Роберт Э. (1988). "Новый подход к проблеме максимального потока". Журнал ACM . 35 (4): 921. doi : 10.1145/48014.61051 . S2CID  52152408.
9. Ахуджа, РК; Магнанти, TL; Орлин, Дж. Б. (1993). Сетевые потоки: теория, алгоритмы и приложения (1-е изд.). Prentice Hall. ISBN 978-0136175490.
10. Шилоах, Йосси; Вишкин, Узи (1982). «Параллельный алгоритм максимального потока O(n2log n)». Журнал алгоритмов . 3 (2): 128–146. doi :10.1016/0196-6774(82)90013-X.
11. Cheriyan, J.; Maheshwari, SN (1988). "Анализ алгоритмов проталкивания предпотока для максимального сетевого потока". Основы технологии программного обеспечения и теоретической информатики . Конспект лекций по информатике. Том 338. стр. 30. doi :10.1007/3-540-50517-2_69. ISBN 978-3-540-50517-4.
12. Черкасский, Борис В.; Голдберг, Эндрю В. (1995). "О реализации метода push-relabel для задачи максимального потока". Целочисленное программирование и комбинаторная оптимизация . Конспект лекций по информатике. Том 920. стр. 157. CiteSeerX 10.1.1.150.3609 . doi :10.1007/3-540-59408-6_49. ISBN  978-3-540-59408-6.
13. Деригс, У.; Мейер, В. (1989). «Реализация алгоритма максимального потока Голдберга? Вычислительное исследование». Zeitschrift für Operations Research . 33 (6): 383. дои : 10.1007/BF01415937. S2CID  39730584.