Изменения

Данный алгоритм заключается в последовательной отмене циклов минимального среднего веса в [[Дополняющая сеть, дополняющий путь|остаточной сети]] посредством их насыщения. Алгоритм работает до тех пор, пока минимальный средний вес циклов не окажется положительным, что будет означать, что поток минимальной стоимости найден.  Более формально:* '''Шаг <tex>1</tex>'''. Рассмотрим некоторый поток <tex>f</tex>. * '''Шаг <tex>2</tex>'''. Найдем цикл <tex>C</tex>, обладающий наименьшим средним весом. Если <tex>\mu (C) \geqslant 0</tex>, то <tex>f</tex> {{---}} поток минимальной стоимости и алгоритм завершается.* '''Шаг <tex>3</tex>'''. Отменим цикл <tex>C</tex>, пустив по нему максимально возможный поток: <tex>f = f + c_{f}(C)\cdot f_{C}</tex>. Перейдем к '''шагу <tex>1</tex>'''.

Для сетей с целочисленными стоимостями на ребрах <tex>O(VE\cdot VE\log{CV})</tex>, с вещественными {{---}} <tex>O(VE\cdot VE^{2}\log{V})</tex>, при этом.В обоих случаях <tex>O(VE)</tex> времени тратится на поиск цикла минимального среднего веса. ===Псевдокод=== '''Edge[]''' findMin('''Graph''' G) '''while''' f <font color="green">// найдём M(C) {{---}} вес минимального цикла</font> C = c : M(c) = <tex>\min\limits_c</tex> M(c) '''if''' M(C) <tex>\geqslant</tex> 0 <font color="green">// Если величина M(C) положительна, то мы нашли f {{---}} поток минимальной стоимости, на этом алгоритм завершается</font> '''return''' f '''else''' <font color="green">// в противном случае отменяем цикл</font> f += c_f * f(C)

Пусть <tex>f</tex> {{---}} поток минимальной стоимости. Введем Введём на нашей сети функцию [[Алгоритм Джонсона|потенциалов]] <tex>\varphi</tex>.

|definition='''Приведенной Приведённой стоимостью''' (англ. ''reduced cost'') ребра назовем следующую величину: <tex>p_{\varphi}(uv)=\varphi(u) + p(uv) - \varphi(v)</tex>.}}Иными словами, приведенная приведённая стоимость {{---}} это сколько нужно потратить денег, чтобы перевезти единицу жидкости из <tex>u</tex> в <tex>v</tex>. (Ее её нужно купить в <tex>u</tex>, перевезти из <tex>u</tex> в <tex>v</tex> и продать в <tex>v</tex>).)

|about=<tex>1</tex>|statement=Если <tex>f</tex> {{---}} поток минимальной стоимости, то <tex>\exists \varphi</tex> такое, что <tex>\forall uv: \; c_{f}(uv) > 0 \qquad implies p_{\varphi}(uv) \geqslant 0</tex>.

:Рассмотрим [[Дополняющая сеть, дополняющий путь|остаточную сеть]] {{---}} граф <tex>G_{f}</tex>. В нем нет отрицательных циклов, так как <tex>f</tex> {{---}} поток минимальной стоимости<ref>[[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]]</ref>.

:Рассмотрим теперь некоторое ребро <tex>uv</tex>. Понятно, что <tex>\varphi(v) \leqslant \varphi(u) + p(uv)</tex>. (Здесь сравниваются минимальный путь <tex>a \rightsquigarrow v</tex> и путь <tex>a \rightsquigarrow u \rightarrow v</tex>). Перенеся <tex>\varphi(v)</tex> в другую часть неравенства, получаем <tex>0 \leqslant \varphi(u) + p(uv) - \varphi(v)</tex> или <tex>0 \leqslant p_{\varphi}(uv)</tex>, что и требовалось доказать.}}

|definition=Будем говорить, что поток <tex>f</tex> {{---}} '''<tex>\varepsilon</tex>-оптимальный''' (англ. ''<tex>\varepsilon</tex>-optimal''), если <tex>\exists \varphi</tex> такая, что <tex>\forall uv: c_{f}(uv) > 0 \qquad implies p_{\varphi}(uv) \geqslant -\varepsilon</tex>.}}

:Поскольку поток Пусть <tex>p'(uv)=p(uv)-\mu^{*}</tex> для любого <tex>uv \in E_{f}</tex> не минимален. Логичным будет также обозначить для некоторого цикла <tex>C</tex> за <tex>\mu'(C)</tex> величину <tex>\dfrac{p'(C)}{\texttt{len}(C)}</tex>. Таким образом, в остаточной сети существует отрицательный циклдля любого цикла <tex>C</tex>, и тогда <tex>\mu'(C)=\mu(C)-\mu^{*} < \geqslant 0</tex>. :ПредположимДалее проведем рассуждения, что аналогичные доказательству [[#lemma1|леммы <tex>f1</tex> является ]].:Добавим вершину <tex>\varepsilona</tex>-оптимальным при и проведем из нее ребро стоимости <tex>0</tex>\varepsilon во все вершины графа <tex> -\mu^G_{*f}</tex>. :Рассмотрим такое ребро В качестве <tex>\varphi(u)</tex> выберем стоимость (считая стоимостью функцию <tex>p'</tex>) минимального пути из <tex>uva</tex>, входящее в цикл <tex>Cu</tex>. :Таким образом, что величина <tex>p_{\varphi}(v) \leqslant \varphi(u) + p'(uv) = \varphi(u) + p(uv)- \mu^{*}</tex> минимальна. Тогда верно следующее: Отсюда получаем, что <tex>p_{\varphi}(uv) \leqslant geqslant \mu^{*}</tex>, то есть для любого ребра <tex>uv</tex> из остаточной сети <tex>p_E_{\varphif}(uv) < -\varepsilon</tex>, что означает, что <tex>f</tex> не является {{---}} <tex>(-\varepsilonmu^{*})</tex>-оптимальным. Получено противоречиеоптимальный, и, значитпо определению <tex>\varepsilon^{*}</tex>, <tex>\varepsilon^{*} \leqslant -\mu^{*}</tex>.

:По [[#lemma3|предыдущей лемме<tex>3</tex>]], <tex>\varepsilon^{*}=-\mu^{*}</tex>, то есть <tex>p_{\varphi}(uv) \geqslant \mu^{*}</tex>. Но поскольку <tex>\mu^{*}</tex> {{---}} средний вес цикла, то <tex>p_{\varphi}(uv) = \mu^{*} = -\varepsilon^{*}</tex>.

|about=<tex>5</tex>|statement=Последовательность из Пусть <tex>f</tex> {{---}} некоторый поток, а <tex>f'</tex> {{---}} поток после <tex>E</tex> отмен циклов минимального среднего веса . Тогда <tex>\varepsilon'^{*} \leqslant \left(1-\dfrac{1}{V}\right)\varepsilon^{*}</tex>, где <tex>\varepsilon'^{*}</tex> {{---}} минимальное <tex>\varepsilon</tex> такое, что поток <tex>f'</tex> <tex>\varepsilon</tex>-оптимальный.|proof=:Изначально любое ребро <tex>uv</tex> удовлетворяет свойству <tex>p_{\varphi}(uv) \geqslant -\varepsilon^{*}</tex>. Отмена цикла добавляет в остаточную сеть <tex>G_{f}</tex> только ребра положительной приведенной стоимости (см. [[#lemma4|лемму <tex>4</tex>]]) и удаляет из сети <tex>G</tex> как минимум одно ребро. Рассмотрим два случая::#Ни один из отмененных циклов не содержал ребер, обладающих неотрицательной приведенной стоимостью. Тогда каждая отмена цикла уменьшает размер допустимого графа <tex>H</tex> и после <tex>E</tex> отмен граф <tex>H</tex> пуст, что означает, что <tex>f'</tex> {{---}} оптимальный поток, то есть <tex>\varepsilon'^{*}=0</tex>.:#Некоторые из отмененных циклов содержали ребра неотрицательной приведенной стоимости. Пусть впервые такое случилось на <tex>i</tex>-ой итерации, и, соответственно, <tex>C_{i}</tex> {{---}} первый из таких циклов. Для <tex>C_{i}</tex> имеем, что каждое его ребро обладает приведенной стоимостью как минимум <tex>-\varepsilon_{i}^{*}</tex> (при этом <tex>\varepsilon'^{*} \leqslant \varepsilon_{i}^{*} \leqslant \varepsilon^{*}</tex> по [[#lemma4|лемме <tex>4</tex>]]), хотя бы одно из ребер <tex>C_{i}</tex> обладает неотрицательной приведенной стоимостью и количество ребер в <tex>C_{i}</tex> не более чем в превышает <tex>V</tex>. Тогда средний вес этого цикла <tex>\mu(C_{i}) = \mu_{i}^{*} \geqslant -\left(1-\dfrac{1}{V}\right)\varepsilon_{i}^{*} \geqslant - \left(1-\dfrac{1}{V}\right)\varepsilon^{*}</tex> раз, и <tex>\varepsilon'^{*} \leqslant \varepsilon_{i}^{*} = -\mu_{i}^{*} \leqslant \left(1-\dfrac{1}{V}\right)\varepsilon^{*}</tex>.}} {{Определение|definition='''<tex>\varepsilon</tex>-фиксированным''' (англ. ''<tex>\varepsilon</tex>-fixed'') будем называть ребро, поток через которое неизменен для любых <tex>\varepsilon</tex>-оптимальных потоков в сети.}} {{Теорема|id=theorem1|statement=Пусть поток <tex>f</tex> является <tex>\varepsilon</tex>-оптимальным с функцией потенциалов <tex>\varphi</tex>. Также пусть для некоторого ребра <tex>uv \; \left|p_{\varphi}(uv)\right| \geqslant 2V\varepsilon</tex>. Тогда ребро <tex>uv</tex> <tex>\varepsilon</tex>-фиксировано.

:По свойству антисимметричности, достаточно будет доказать теорему для случая <tex>p_{\varphi}(uv) \geqslant 2V\varepsilon</tex>. :Рассмотрим такую последовательность. Изначально любое ребро такой поток <tex>f'</tex>, что <tex>f'(uv) \neq f(uv)</tex> удовлетворяет свойству . Поскольку <tex>p_{\varphi}(uv) \geqslant -2V\varepsilon > \varepsilon^{*}</tex>. Отмена цикла добавляет в остаточную сеть , поток по ребру <tex>uv</tex> должен быть как можно меньше, то есть <tex>G_{f}(uv) = -c(uv)</tex> только ребра положительной приведенной стоимости , и тогда раз <tex>f'(uv) \neq f(см. [[#lemma4|предыдущую лемму]]uv) и удаляет из сети </tex>, то <tex>Gf'(uv) > f(uv)</tex> как минимум одно ребро. Рассмотрим два случая: :#Ни один из отмененных циклов не содержал реберПокажем теперь, обладающих неотрицательной приведенной стоимостью. Тогда каждая отмена цикла уменьшает размер допустимого графа что <tex>Hf'</tex> и после не <tex>\varepsilon</tex>-оптимальный.:Обозначим за <tex>EG_{>}</tex> отмен граф подграф <tex>HG</tex> пусттакой, что означает<tex>G_{>}=(V, что \{uv \in E \;|\; f'(uv) > f(uv) \})</tex>. Рассмотрим некоторое ребро <tex>fuv</tex> в <tex>G_{{--->}} оптимальный поток</tex>. Поскольку <tex>f</tex> и <tex>f'</tex> являются циркуляциями, то есть в <tex>\varepsilon^G_{*>}=0</tex> должен содержаться простой цикл <tex>C</tex>, проходящий через <tex>uv</tex>.:#Некоторые из отмененных циклов содержали Поскольку все ребра неотрицательной приведенной стоимости. Пусть в <tex>C</tex> {{---}} первый из таких циклов. Для остаточные, стоимость <tex>C</tex> имеем, что каждое его ребро обладает приведенной стоимостью как минимум не меньше <tex>p_{\varphi}(uv) - (\texttt{len}(C)-1)\varepsilon \geqslant 2V\varepsilon - (V-1)\varepsilon > V\varepsilon</tex>, хотя бы одно из ребер .:Теперь рассмотрим цикл <tex>\overline{C}</tex> обладает неотрицательной приведенной стоимостью, количество ребер в который получен из <tex>C</tex> не превышает разворотом всех его ребер. Заметим, что <tex>V\overline{C}</tex>. Тогда средний вес этого цикла является циклом в <tex>\muG_{<}=(C) = V,\mu^{*} uv \in E \geqslant -;|\left; f'(1-uv) < f(uv)\dfrac{1})</tex> и, соответственно, циклом в <tex>G_{Vf}\right)\varepsilon</tex>. Тогда непосредственно перед отменой По свойству антисимметричности, стоимость <tex>\overline{C}</tex>меньше, чем <tex>-\mu^{*}=V\varepsilon^{*} </tex> и, таким образом, <tex>\leqslant \leftmu(1-\dfracoverline{1C}{V}\right)< -\varepsilon</tex> (. Откуда по [[#lemma3|лемме<tex>3</tex>]]). Поскольку мы [[#lemma4|знаем]]имеем, что <tex>f'</tex> не <tex>\varepsilon^{*}</tex> не увеличивается, доказываемое утверждение верно-оптимален.}}

|about=доказательство оценки времени работы алгоритмав случае вещественных стоимостей

:Чтобы доказать его, рассмотрим некоторую группу итераций. Пусть <tex>f</tex> {{---}} поток до первой итерации, а <tex>f'</tex> {{---}} после последней итерации этой группы. Обозначим за <tex>\varepsilon'^{*}</tex> минимальное <tex>\varepsilon</tex> такое, что поток <tex>f'</tex> <tex>\varepsilon</tex>-оптимальный, а за <tex>\varphi'</tex> {{---}} функцию потенциалов такую, что <tex>f'</tex> удовлетворяет свойству <tex>\varepsilon'^{*}</tex>-оптимальности. Выбор <tex>k</tex> и [[#lemma5|предыдущая лемма<tex>5</tex>]] дают нам следующее неравенство: <tex>\varepsilon'^{*} \leqslant \varepsilon^{*} \left(1-\dfrac{1}{V} \right)^{V(\log V + 1)} \leqslant \dfrac{\varepsilon^{*}}{2V}</tex>. :Рассмотрим цикл <tex>C</tex>, отмененный на первой итерации рассматриваемой группы. Поскольку средний вес цикла <tex>C</tex> равен <tex>-\varepsilon^{*}</tex> (см. [[#lemma3|лемму<tex>3</tex>]]), некоторое ребро <tex>uv</tex> цикла <tex>C</tex> должно иметь приведенную стоимость <tex>p_{\varphi'}(uv) \leqslant -\varepsilon^{*} \leqslant -2V\varepsilon'^{*}</tex>. Таким образом, поток на ребре <tex>uv</tex> не изменится при итерациях, происходящих после этой группы. Таким образом, по [[#theorem1|теореме]] каждая группа фиксирует поток на независимом ребре.}}

Такой Тогда, если <tex>C_{max}</tex> и <tex>C_{min}</tex> {{---}} максимальная и минимальная возможные величины среднего веса цикла соответственно, такой алгоритм для вещественных значений весов ребер будет работать за <tex>O\left(\texttt{log} \dfrac{1C_{max}-C_{min}}{\varepsilon} \cdot EV\right)</tex>, где <tex>\varepsilon</tex> {{---}} точность выбора среднего веса цикла.При этом для целочисленных значений на ребрах точность выбора величины среднего веса циклане может превысить <tex>\dfrac{1}{V}</tex>, что дает нам оценку <tex>O\left(\log (V(C_{max}-C_{min})) \cdot EV\right)</tex>. ====Псевдокод====  '''func''' findMinCycleBinarySearch('''int''' l, '''int''' r) <font color="green">// находим среднюю величину <tex>m</tex></font> m = (l + r) / 2 <font color="green">// вычитаем её из веса каждого ребра в сети</font> '''for''' e '''in''' edges e.weight -= m '''while''' l > r - 1 <!-----<font color="green">// добавляем мнимую вершину <tex>s</tex> и проводим рёбра нулевого веса в каждую вершину графа</font>---------> '''if''' <tex>\exists</tex>C : M(C) < 0 <!--- cho-t xz za4em C: mb exists? eee ugadala)0))---> <font color="green">// если есть отрицательный цикл, то веса циклов находятся в диапазоне <tex>[l;m]</tex> // рассмотрим этот промежуток</font> findMinCycleBinarySearch (l, m) '''else''' <font color="green">// иначе запускаем двоичный поиск на отрезке <tex>[m;r]</tex></font> findMinCycleBinarySearch (m, r)

Добавим к нашему графу вершину <tex>s</tex> и ребра рёбра из нее неё во все остальные вершины.

Этот алогоритм алгоритм работает за <tex>O(VE)</tex><ref>[[Алгоритм Форда-Беллмана #Сложность| Сложность алгоритма Форда-Беллмана]]</ref>. ====Псевдокод==== '''func''' findMinCycle('''Graph''' G) <font color="green">// вводим мнимую вершину <tex>s</tex>, от которой проведём рёбра нулевого веса в каждую вершину графа</font> '''Node''' s '''Edge[]''' e insert(s) i = 0 '''for''' u '''in''' G e[i].begin = s e[i].end = u e[i].weight = 0 i++ <font color="green">// строим матрицу кратчайших расстояний, запустив алгоритм Форда-Беллмана из вершины <tex>s</tex></font> fordBellman(s) <font color="green">// <tex>m</tex> {{---}} длина оптимального цикла</font> m = <tex>\min\limits_{u} {\max\limits_{k} }</tex>((d[n][u] - d[k][u]) / (n - k)) <!-----<font color="green">// запомнив значения <tex>u</tex> и <tex>k</tex>, дающих оптимальный результат, найдём цикл</font>---------> <!----чуть не забыла про отступы, дура тупая----->