Нажать – изменить алгоритм максимального потока

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

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

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

История [ править ]

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

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

Концепции [ править ]

Определения и обозначения [ править ]

Позволять:

$G = (V, E)$ - сеть с функцией пропускной способности $c : V \times V \to ℝ \infty$ ,
$F = (G, C, ев, т)$ сетевой поток , где $S \in V$ и $т \in V$ выбраны исходные и поглотителей вершины соответственно,
$F : V \times V \to ℝ$ обозначают предварительный поток в $F$ ,
$x f : V \to ℝ$ обозначает избыточную функцию по отношению к потоку $f$ , определяемую формулой $x f (u) = \sum v \in V f (v, u) - \sum v \in V f (u, v)$ ,
$c f : V \times V \to ℝ \infty$ обозначает функцию остаточной пропускной способности по отношению к потоку $f$ , определяемую формулой $c f (e) = c (e) - f (e)$ ,
$E f \subset E$ - ребра, где $f < c$ ,

а также

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

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

Действующая маркировка :

𝓁 (u) \leq 𝓁 (v) + 1

для всех

(u, v) \in E f

Состояние источника :

𝓁 (s) = | V |

Консервация раковины :

𝓁 (t) = 0

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

Дуга $(u, v) \in E f$ называется допустимой, если $𝓁 (u) = 𝓁 (v) + 1$ . Допустимая сеть $G F (V, Ē е)$ состоит из множества дуг $е \in E F$ , которые являются допустимыми. Допустимая сеть ациклична.

Операции [ править ]

Инициализация [ править ]

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

Нажмите [ редактировать ]

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

push (u, v): assert x _f [u]> 0 и 𝓁 [u] == 𝓁 [v] + 1 Δ = min (x _f [u], c [u] [v] - f [u] [v]) f [u] [v] + = Δ f [v] [u] - = Δ x _f [u] - = Δ x _f [v] + = Δ

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

Переименовать [ править ]

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

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

Эффекты push и повторной маркировки [ править ]

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

Для операции проталкивания на допустимой дуге $(u, v)$ он может добавить дугу $(v, u)$ к $E f$ , где $𝓁 (v) = 𝓁 (u) - 1 \leq (u) + 1$ ; он также может удалить дугу $(u, v)$ из $E f$ , где эффективно снимает ограничение $𝓁 (u) \leq 𝓁 (v) + 1$ .

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

Общий алгоритм push – relabel [ править ]

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

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

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

Правильность [ править ]

Во время выполнения алгоритм поддерживает условие, что $𝓁$ является допустимой $меткой$ . Это можно доказать, исследуя влияние операций push и reabel на функцию label $𝓁$ . Операция переназначения увеличивает значение метки на соответствующий минимум плюс один, который всегда будет удовлетворять $ограничению 𝓁 (u) \leq 𝓁 (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)$ из $G f$ снимает соответствующее ограничение, поскольку допустимое свойство маркировки $𝓁 (u) \leq 𝓁 (v) + 1$ применяется только к остаточным дугам в $G f$ .^[8]

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

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

Сложность времени [ править ]

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

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

Каждый насыщающий толчок допустимой дуге $(u, v)$ удаляет дугу из $G f$ . Для дуги с возможностью повторного введения $G F$ для другого насыщающего толчка, $v$ должен быть сначала перемаркированные, с последующим нажатием на дуге $(об, ¯u)$ , то $у$ должен быть перемаркированные. При этом $𝓁 (u)$ увеличивается как минимум на два. Следовательно, на $($ $u$ $,$ $v$ $)$ имеется $O (V)$ насыщающих толчков., а общее количество насыщающих толчков не превышает $2 | V || E |$ . Это приводит к ограничению по времени $O (VE)$ для операций насыщающей проталкивания.

Ограничить количество ненасыщающих толчков можно с помощью потенциального аргумента . Мы используем потенциальную функцию $Φ = \sum [u \in V \land x f (u)> 0] 𝓁 (u)$ (т.е. $Φ$ - это сумма меток всех активных узлов). Очевидно, что изначально $Φ$ равно $0$ и остается неотрицательной на протяжении всего выполнения алгоритма. И повторная маркировка, и насыщающие толчки могут увеличивать $Φ$ . Однако значение $Φ$ должен быть равен 0 при завершении, поскольку в конце выполнения алгоритма не может быть никаких оставшихся активных узлов. Это означает, что во время выполнения алгоритма ненасыщающие нажатия должны компенсировать разницу между операциями переназначения и насыщения, чтобы $Φ$ завершилась со значением 0. Операция переназначения может увеличить $Φ не$ более чем на $(2 | V). | - 1) (| V | - 2)$ . Насыщающий толчок на $(u, v)$ активирует $v,$ если он был неактивен до толчка, увеличивая $Φ не$ более чем на $2 | V | - 1$ . Следовательно, суммарный вклад всех насыщающих операций подталкивания в $Φ$ не превосходит $(2 | V | - 1) (2 | V || E |)$ . Ненасыщающий толчок $(u, v)$ всегда дезактивирует $u$ , но он также может активировать $v,$ как в насыщающем толчке. В результате он уменьшает $Φ$ как минимум на $𝓁 (u) - 𝓁 (v) = 1$ . Поскольку повторные метки и насыщающие толчки увеличивают $Φ$ , общее количество ненасыщающих толчков должно составлять разницу $(2 | V | - 1) (| V | - 2) + (2 | V | - 1) (2 | V || E |) \leq 4 | V | 2 | E |$ . Это приводит к ограничению времени $O (V 2 E)$ для ненасыщающих операций проталкивания.

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

Пример [ править ]

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

Окончательный график сети максимального потока

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

Алгоритм Операция (ы)	Остаточный график
Инициализируйте остаточный график, установив предварительный поток на значения 0 и инициализируя маркировку.
Начальный насыщающий толчок выполняется по всем дугам предварительного потока, выходящим из источника, $s$ .
Узел $a$ переименован, чтобы направить его избыточный поток к раковине $t$ . Затем избыток в точке $a$ перемещается в точку $b,$ затем в $точку d$ в двух последовательных толчках насыщения; которые до сих пор оставляет с некоторым избытком.

Еще раз, $a$ меняют метку, чтобы протолкнуть его избыток вдоль последнего оставшегося положительного остатка (т. Е. Вернуть избыток к $s$ ). Затем узел $a$ удаляется из набора активных узлов.

Пометьте $b,$ а затем переместите его избыток к $t$ и $c$ .
Пометьте $c,$ а затем переместите его избыток на $d$ .
Пометьте $d,$ а затем переместите его избыток к $t$ .
Это оставляет узел $b$ в качестве единственного оставшегося активного узла, но он не может подтолкнуть свой избыточный поток к приемнику. Пометьте $b,$ а затем протолкните его избыток к источнику $s$ через узел $a$ .

Нажмите на последний бит избыток в $виде$ обратно к источнику, $S$ . Нет оставшихся активных узлов. Алгоритм завершается и возвращает максимальный поток графика (как показано выше).

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

Практические реализации [ править ]

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

Структура данных "ток-дуга" и операция разряда [ править ]

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

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

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

Правила выбора активного узла [ править ]

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

Правило выбора FIFO [ править ]

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

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

Правило выбора переназначения на передний план [ править ]

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

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

Правило выбора наивысшего ярлыка [ править ]

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

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

Методы реализации [ править ]

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

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

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

Примеры реализации [ править ]

C реализация

#include  <stdlib.h>#include  <stdio.h>#define NODES 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  =  БЕСКОНЕЧНО ;  for  ( v  =  0 ;  v  <  NODES ;  v ++ )  {  if  ( C [ u ] [ v ]  - F [ u ] [ v ]  >  0 )  {  min_height  =  MIN ( min_height ,  height [ v ]);  высота [ u ]  =  min_height  +  1 ;  }  } };пустая  разрядка ( const  int  *  const  *  C ,  int  **  F ,  int  * превышение ,  int  * высота ,  int  * замечено ,  int  u )  {  while  ( Excess [ u ]  >  0 )  {  if  ( seen [ u ]  <  УЗЛЫ )  {  int  v  =  видел [ u];  если  (( C [ u ] [ v ]  -  F [ u ] [ v ]  >  0 )  &&  ( высота [ u ]  >  height [ v ]))  {  push ( C ,  F ,  избыток ,  u ,  v );  }  else  {  видел [ u ]  + =  1 ;  }  }  else  {  relabel( C ,  F ,  высота ,  u );  видел [ u ]  =  0 ;  }  } }void  moveToFront ( int  i ,  int  * A )  {  int  temp  =  A [ я ];  int  n ;  для  ( n  =  i ;  n  >  0 ;  n - )  {  A [ n ]  =  A [ n -1 ];  }  A [ 0 ]  =  temp ; }INT  pushRelabel ( Const  INT  *  сопзЬ  *  C ,  INT  **  F ,  INT  источник ,  ИНТ  раковина )  {  INT  * превышение ,  * высота ,  * список ,  * видел ,  я ,  р ; избыток  =  ( int  * )  calloc ( NODES ,  sizeof ( int ));  высота  =  ( int  * )  calloc ( УЗЛЫ ,  sizeof ( int ));  замечено  =  ( int  * )  calloc ( NODES ,  sizeof ( int )); список  =  ( int  * )  calloc (( УЗЛЫ -2 ),  sizeof ( int )); for  ( i  =  0 ,  p  =  0 ;  i  <  NODES ;  i ++ ) {  if  (( i  ! =  источник )  &&  ( i  ! =  сток ))  {  list [ p ]  =  i ;  p ++ ;  }  } высота [ источник ]  =  УЗЛЫ ;  избыток [ источник ]  =  БЕСКОНЕЧНО ;  for  ( i  =  0 ;  i  <  NODES ;  i ++ )  push ( C ,  F ,  избыток ,  источник ,  i ); р  =  0 ;  в то время как  ( p  <  УЗЛЫ  -  2 )  {  int  u  =  list [ p ];  int  old_height  =  высота [ u ];  разряд ( C ,  F ,  превышение ,  высота ,  видно ,  u );  if  ( height [ u ]  >  old_height )  {  moveToFront ( p , список );  р  =  0 ;  }  else  {  p  + =  1 ;  }  }  int  maxflow  =  0 ;  для  ( я  =  0 ;  я  <  УЗЛЫ ;  я ++ )  maxflow  + =  F [ источник ] [ я ]; бесплатно ( список ); бесплатно ( просмотрено );  свободный ( высота );  бесплатно ( франшиза ); return  maxflow ; }void  printMatrix ( const  int  *  const  *  M )  {  int  я ,  j ;  for  ( i  =  0 ;  i  <  NODES ;  i ++ )  {  for  ( j  =  0 ;  j  <  NODES ;  j ++ )  printf ( "% d \ t " , M [ i ] [ j ]);  printf (" \ п " );  } }int  main ( void )  {  int  ** поток ,  ** мощности ,  я ;  flow  =  ( int  ** )  calloc ( УЗЛЫ ,  sizeof ( int * ));  capacity  =  ( int  ** )  calloc ( NODES ,  sizeof ( int * ));  для  ( i  =  0 ;  i  <  УЗЛЫ ; я ++ )  {  поток [ я ]  =  ( int  * )  calloc ( УЗЛЫ ,  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 ( "Потоки: \ п " );  printMatrix ( поток ); возврат  0 ; }

Реализация Python

Защиту  relabel_to_front ( C ,  источник :  INT ,  раковина :  INT )  ->  INT :  п  =  Len ( C )  # C матрица емкости  F  =  [[ 0 ]  *  п  для  _  в  интервале ( п )]  # остаточная емкость от и к v - это C [u] [v] - F [u] [v] height  =  [ 0 ]  *  n  # высота  превышения  узла =  [ 0 ]  *  n  # поток в узел минус поток от узла  замечен  =  [ 0 ]  *  n  # соседей, замеченных с момента последней перемаркировки  # узла "queue"  nodelist  =  [ i  for  i  в  диапазоне ( n ),  если  i  ! =  источник  и  i  ! =  сток ] def  push ( u ,  v ):  send  =  min ( превышение [ u ],  C [ u ] [ v ]  -  F [ u ] [ v ])  F [ u ] [ v ]  + =  отправить  F [ v ] [ u ]  - =  отправить  лишнее [ u ]  - =  отправить  лишнее [ v ]  + =  отправить def  relabel ( u ):  # Найти наименьшую новую высоту, делающую возможным толчок,  # если такой толчок вообще возможен.  min_height  =  ∞  для  v  в  xrange ( n ):  если  C [ u ] [ v ]  -  F [ u ] [ v ]  >  0 :  min_height  =  min ( min_height ,  height [ v ])  height [ u ]  =  min_height +  1 def  разрядка ( u ): в  то время как  превышение [ u ]  >  0 :  если  видно [ u ]  <  n :  # проверить следующего соседа  v  =  видно [ u ],  если  C [ u ] [ v ]  -  F [ u ] [ v ]  >  0  и  высота [ u ]  >  высота [ v ]:  push (u ,  v )  else :  seen [ u ]  + =  1  else :  # мы проверили всех соседей. необходимо изменить метку  relabel ( u )  visible [ u ]  =  0 height [ source ]  =  n  # самый длинный путь от источника до приемника меньше n long  превышение [ источник ]  =  ∞  # отправить как можно больше потока соседям источника  для  v  в  диапазоне ( n ):  push ( source ,  v ) р  =  0 ,  а  р  <  LEN ( нодлиста ):  U  =  нодлиста [ р ]  old_height  =  высота [ U ]  разряда ( U ) ,  если  высота [ U ]  >  old_height :  нодлиста . insert ( 0 ,  nodelist . pop ( p ))  # перейти к  началу списка p  =  0  # начать с начала списка  else:  p  + =  1  сумма возврата ( F [ источник ])

Ссылки [ править ]

^ a b c Кормен, TH ; Лейзерсон, CE ; Ривест, Р.Л . ; Стейн, К. (2001). «§26 Максимальный поток». Введение в алгоритмы (2-е изд.). MIT Press. стр. 643 -698. ISBN 978-0262032933.
^ a b c d e f g Гольдберг, А. В.; Tarjan, RE (1986). «Новый подход к проблеме максимального потока». Материалы восемнадцатого ежегодного симпозиума ACM по теории вычислений - STOC '86 . п. 136. DOI : 10.1145 / 12130.12144 . ISBN 978-0897911931.
^ a b Ахуджа, Равиндра К .; Кодиалам, Мурали; Мишра, Аджай К .; Орлин, Джеймс Б. (1997). «Вычислительные исследования алгоритмов максимального потока». Европейский журнал операционных исследований . 97 (3): 509. CiteSeerX 10.1.1.297.2945 . DOI : 10.1016 / S0377-2217 (96) 00269-X .
^ a b c Голдберг, Эндрю В. (2008). «Частичный алгоритм дополнения – перемаркировки для задачи о максимальном потоке». Алгоритмы - ESA 2008 . Конспект лекций по информатике. 5193 . С. 466–477. CiteSeerX 10.1.1.150.5103 . DOI : 10.1007 / 978-3-540-87744-8_39 . ISBN 978-3-540-87743-1.
^ Голдберг, Эндрю V (1997). «Эффективная реализация масштабируемого алгоритма потока минимальной стоимости». Журнал алгоритмов . 22 : 1–29. DOI : 10.1006 / jagm.1995.0805 .
^ Ахуджа, Равиндра К .; Орлин, Джеймс Б. (1991). «Направленные на расстояние алгоритмы увеличения траектории для задач максимального потока и параметрического максимального потока». Логистика военно-морских исследований . 38 (3): 413. CiteSeerX 10.1.1.297.5698 . DOI : 10.1002 / 1520-6750 (199106) 38: 3 <413 :: АИД-NAV3220380310> 3.0.CO; 2-J .
^ Голдберг, Эндрю V .; Тарджан, Роберт Э. (2014). «Эффективные алгоритмы максимального потока». Коммуникации ACM . 57 (8): 82. DOI : 10,1145 / 2628036 .
^ a b c d Голдберг, Эндрю В.; Тарджан, Роберт Э. (1988). «Новый подход к проблеме максимального расхода». Журнал ACM . 35 (4): 921. DOI : 10.1145 / 48014.61051 .
^ а б Ахуджа, РК; Magnanti, TL; Орлин, Дж. Б. (1993). Сетевые потоки: теория, алгоритмы и приложения (1-е изд.). Прентис Холл. ISBN 978-0136175490.
^ Шилоах, Йосси; Вишкин, Узи (1982). «Параллельный алгоритм максимального потока O (n2log n)». Журнал алгоритмов . 3 (2): 128–146. DOI : 10.1016 / 0196-6774 (82) 90013-X .
^ Cheriyan, J .; Махешвари, С. Н. (1988). «Анализ алгоритмов проталкивания предпотока для максимального сетевого потока». Основы программных технологий и теоретической информатики . Конспект лекций по информатике. 338 . п. 30. DOI : 10.1007 / 3-540-50517-2_69 . ISBN 978-3-540-50517-4.
^ Черкасский, Борис В .; Гольдберг, Эндрю В. (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.
^ Derigs, U .; Мейер, В. (1989). «Реализация алгоритма максимального потока Голдберга? Вычислительное исследование». ZOR Zeitschrift für Методы исследования операций и модели исследования операций . 33 (6): 383. DOI : 10.1007 / BF01415937 .

[clrs26-1] Кормен, TH ; Лейзерсон, CE ; Ривест, Р.Л . ; Стейн, К. (2001). «§26 Максимальный поток». Введение в алгоритмы (2-е изд.). MIT Press. стр. 643 -698. ISBN 978-0262032933.

[goldberg86-2] Гольдберг, А. В.; Tarjan, RE (1986). «Новый подход к проблеме максимального потока». Материалы восемнадцатого ежегодного симпозиума ACM по теории вычислений - STOC '86 . п. 136. DOI : 10.1145 / 12130.12144 . ISBN 978-0897911931.

[ahuja97-3] Ахуджа, Равиндра К .; Кодиалам, Мурали; Мишра, Аджай К .; Орлин, Джеймс Б. (1997). «Вычислительные исследования алгоритмов максимального потока». Европейский журнал операционных исследований . 97 (3): 509. CiteSeerX 10.1.1.297.2945 . DOI : 10.1016 / S0377-2217 (96) 00269-X .

[goldberg08-4] Голдберг, Эндрю В. (2008). «Частичный алгоритм дополнения – перемаркировки для задачи о максимальном потоке». Алгоритмы - ESA 2008 . Конспект лекций по информатике. 5193 . С. 466–477. CiteSeerX 10.1.1.150.5103 . DOI : 10.1007 / 978-3-540-87744-8_39 . ISBN 978-3-540-87743-1.

[goldberg97-5] Голдберг, Эндрю V (1997). «Эффективная реализация масштабируемого алгоритма потока минимальной стоимости». Журнал алгоритмов . 22 : 1–29. DOI : 10.1006 / jagm.1995.0805 .

[ahuja91-6] Ахуджа, Равиндра К .; Орлин, Джеймс Б. (1991). «Направленные на расстояние алгоритмы увеличения траектории для задач максимального потока и параметрического максимального потока». Логистика военно-морских исследований . 38 (3): 413. CiteSeerX 10.1.1.297.5698 . DOI : 10.1002 / 1520-6750 (199106) 38: 3 <413 :: АИД-NAV3220380310> 3.0.CO; 2-J .

[goldberg2014-7] Голдберг, Эндрю V .; Тарджан, Роберт Э. (2014). «Эффективные алгоритмы максимального потока». Коммуникации ACM . 57 (8): 82. DOI : 10,1145 / 2628036 .

[goldberg88-8] Голдберг, Эндрю В.; Тарджан, Роберт Э. (1988). «Новый подход к проблеме максимального расхода». Журнал ACM . 35 (4): 921. DOI : 10.1145 / 48014.61051 .

[amo93-9] а б Ахуджа, РК; Magnanti, TL; Орлин, Дж. Б. (1993). Сетевые потоки: теория, алгоритмы и приложения (1-е изд.). Прентис Холл. ISBN 978-0136175490.

[sv82-10] Шилоах, Йосси; Вишкин, Узи (1982). «Параллельный алгоритм максимального потока O (n2log n)». Журнал алгоритмов . 3 (2): 128–146. DOI : 10.1016 / 0196-6774 (82) 90013-X .

[cheriyan88-11] Cheriyan, J .; Махешвари, С. Н. (1988). «Анализ алгоритмов проталкивания предпотока для максимального сетевого потока». Основы программных технологий и теоретической информатики . Конспект лекций по информатике. 338 . п. 30. DOI : 10.1007 / 3-540-50517-2_69 . ISBN 978-3-540-50517-4.

[cherkassky95-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.

[derigs89-13] Derigs, U .; Мейер, В. (1989). «Реализация алгоритма максимального потока Голдберга? Вычислительное исследование». ZOR Zeitschrift für Методы исследования операций и модели исследования операций . 33 (6): 383. DOI : 10.1007 / BF01415937 .

[1]