Изменения

В статье описывается один из сильно полиномиальных алгоритмов решения [[Поток минимальной стоимости #Задача о потоке минимальной стоимости|задачи о поиске потока минимальной стоимости]].==Алгоритм ==Приведенный алгоритм основан на идее [[Поток минимальной стоимости #Метод устранения отрицательных циклов в остаточной сети|алгоритма Клейна отмены цикла отрицательного веса]]. Выбор цикла минимального среднего весавместо случайного делает алгоритм сильно полиномиальным.{{Определение|definition='''Сильно полиномиальными''' (англ. ''strongly polynomial'') в контексте данной задачи называются алгоритмы, чья сложность полиномиально зависит от <tex>V</tex> и <tex>E</tex>.}}===Описание===Обозначим как <tex>c_{f}(C)</tex> остаточную [[Определение сети, потока|пропускную способность]] цикла <tex>C</tex> при протекании в сети потока <tex>f</tex>.Cтоимость цикла <tex>C</tex> обозначим за <tex>p(C)</tex>, а длину (число входящих в него ребер) {{---}} за <tex>\texttt{len}(C)</tex>.{{Определение|definition='''Средним весом''' (англ. ''mean weight'') цикла будем называть отношение его стоимости к его длине <tex>\mu (C)=\dfrac{p(C)}{\texttt{len}(C)}</tex>}}Данный алгоритм заключается в последовательной отмене циклов минимального среднего веса в [[Дополняющая сеть, дополняющий путь|остаточной сети]] посредством их насыщения. Алгоритм работает до тех пор, пока минимальный средний вес циклов не окажется положительным, что будет означать, что поток минимальной стоимости найден.  Более формально:* '''Шаг <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>). {{Лемма|id=lemma1|about=<tex>1</tex>|statement=Если <tex>f</tex> {{---}} поток минимальной стоимости, то <tex>\exists \varphi</tex> такое, что <tex>\forall uv: \; c_{f}(uv) > 0 \implies p_{\varphi}(uv) \geqslant 0</tex>.|proof=:Рассмотрим остаточную сеть {{---}} граф <tex>G_{f}</tex>. В нем нет отрицательных циклов, так как <tex>f</tex> {{---}} поток минимальной стоимости<ref>[[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]]</ref>.  :Добавим вершину <tex>a</tex> и проведем из нее ребро стоимости <tex>0</tex> во все вершины графа <tex>G_{f}</tex>. В качестве <tex>\varphi(u)</tex> выберем стоимость минимального пути из <tex>a</tex> в <tex>u</tex>. :Рассмотрим теперь некоторое ребро <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>Vf</tex> {{---}} числа вершин и '''<tex>E\varepsilon</tex> {{--оптимальный''' (англ. ''<tex>\varepsilon</tex>-optimal''), если <tex>\exists \varphi</tex> такая, что <tex>\forall uv: c_{f}(uv) > 0 \implies p_{\varphi} числа ребер графа(uv) \geqslant -\varepsilon</tex>.}}

{{Лемма|id=lemma2|about=<tex>2</tex>|statement=Описание алгоритма==Если стоимости целочисленны и поток <tex>f</tex> {{---}} <tex>\varepsilon</tex>-оптимальный, где <tex>\varepsilon < \dfrac{1}{V}</tex>, то <tex>f</tex> {{---}} поток минимальной стоимости.|proof=:Рассмотрим некоторый цикл в остаточной сети <tex>C</tex>. Заметим, что <tex>p(C)=p_{\varphi}(C)</tex> (для доказательства этого факта достаточно расписать <tex>p_{\varphi}(C)</tex> по определению). :Возьмем <tex>\varphi</tex> такое, что стоимости всех ребер в <tex>C</tex> не меньше <tex>-\varepsilon</tex>. Обозначим его Тогда стоимость за всего цикла <tex>p_{\varphi}(C)\geqslant -V\cdot \varepsilon</tex> (в цикле не больше <tex>V</tex> ребер). Таким образом, <tex>p_{\varphi}(C) > -1</tex>, то есть <tex>p(C) > -1</tex>. Но исходные пропускные способности были целочисленными, поэтому <tex>p(C)\geqslant 0</tex>, а его длину (число реберэто означает, входящих что в остаточной сети нет отрицательных циклов, и, соответственно, <tex>f</tex> {{---}} поток минимальной стоимости.}} Обозначим за <tex>\mu^{*}</tex> минимальную величину среди средних весов циклов для потока <tex>f</tex>, а за <tex>\varepsilon^{*}</tex> минимальное <tex>\varepsilon</tex> такое, что поток <tex>f</tex> {{---}} <tex>\varepsilon</tex>-оптимальный.{{Лемма|id=lemma3|about=<tex>3</tex>|statement=Если <tex>f</tex> {{---}} поток не минимальной стоимости, то <tex>\varepsilon^{*}=-\mu^{*}</tex>.|proof=:Пусть <tex>C</tex> {{---}} циклминимального среднего веса в остаточной сети.*Покажем, что <tex>\mu^{*} \geqslant -\varepsilon^{*}</tex>.:Поскольку поток <tex>f</tex> является <tex>\varepsilon^{*}</tex>-оптимальным, верно следующее: <tex>p(C) = p_{\varphi}(C) \geqslant -\texttt{len}(C) \cdot \varepsilon^{*}</tex> или <tex>\dfrac{p(C)}{\texttt{len}(C)} \geqslant -\varepsilon^{*} </tex>, то есть <tex>\mu(C)=\mu^{*} \geqslant -\varepsilon^{*}</tex>. *Теперь покажем, что <tex>\mu^{*} \leqslant -\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>1</tex>]].:Добавим вершину <tex>a</tex> и проведем из нее ребро стоимости <tex>0</tex> во все вершины графа <tex>G_{f}</tex>. В качестве <tex>\varphi(u)</tex> выберем стоимость (считая стоимостью функцию <tex>p'</tex>) минимального пути из <tex>a</tex> в <tex>u</tex>. :Таким образом, <tex>\varphi(v) \leqslant \varphi(u) + p'(uv) = \varphi(u) + p(uv) - \mu^{*}</tex>.Отсюда получаем, что <tex>p_{\varphi}(uv) \geqslant \mu^{*}</tex> для любого ребра <tex>uv</tex> из остаточной сети <tex>E_{f}</tex>, что означает, что <tex>f</tex> {{---}} <tex>(-\mu^{*})</tex>-оптимальный, и, по определению <tex>\varepsilon^{*}</tex>, <tex>\varepsilon^{*} \leqslant -\mu^{*}</tex>.}} {{Лемма|id=lemma4|about=<tex>4</tex>|statement=Отмена цикла минимального среднего веса не увеличивает <tex>\varepsilon^{*}</tex>.|proof=:Пусть <tex>C</tex> {{---}} цикл минимального среднего веса, который мы хотим отменить на текущем шаге нашего алгоритма. Перед тем, как мы отменим этот цикл, любое ребро в остаточной сети, в том числе, любое входящее в цикл <tex>C</tex> ребро <tex>uv</tex> удовлетворяет свойству <tex>\varepsilon^{*}</tex>-оптимальности: <tex>p_{\varphi}(uv) \geqslant -\varepsilon^{*}</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>. :По [[Поток минимальной стоимости #Свойства стоимости|свойству антисимметричности потока]], после отмены цикла <tex>C</tex>, в остаточной сети появятся ребра стоимости <tex>\varepsilon</tex>. Таким образом, свойство <tex>p_{\varphi}(uv) \geqslant -\varepsilon</tex> все еще выполняется.}}

|definition='''Средним весом Допустимым графом''' (англ. ''admissible graph'') будем называть такой подграф остаточной сети, что он включает только ребра отрицательной приведенной стоимости. <tex>H=\{uv \in E_{f}\;|\; p_{\varphi}(uv) < 0\}</tex>}} {{Лемма|id=lemma5|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>-фиксировано.|proof=:По свойству антисимметричности, достаточно будет доказать теорему для случая <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>f(uv) = -c(uv)</tex>, и тогда раз <tex>f'(uv) \neq f(uv)</tex>, то <tex>f'(uv) > f(uv)</tex>. :Покажем теперь, что <tex>f'</tex> не <tex>\varepsilon</tex>-оптимальный.:Обозначим за <tex>G_{>}</tex> подграф <tex>G</tex> такой, что <tex>G_{>}=(V, \{uv \in E \;|\; f'(uv) > f(uv) \})</tex>. Рассмотрим некоторое ребро <tex>uv</tex> в <tex>G_{>}</tex>. Поскольку <tex>f</tex> и <tex>f'</tex> являются циркуляциями, в <tex>G_{>}</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>\overline{C}</tex> является циклом в <tex>G_{<}=(V,\{uv \in E \;|\; f'(uv) < f(uv)\})</tex> и, соответственно, циклом в <tex>G_{f}</tex>. По свойству антисимметричности, стоимость <tex>\overline{C}</tex> меньше, чем <tex>-V\varepsilon</tex> и, таким образом, <tex>\mu (\overline{C})< -\varepsilon</tex>. Откуда по [[#lemma3|лемме <tex>3</tex>]] имеем, что <tex>f'</tex> не <tex>\varepsilon</tex>-оптимален.}} {{Лемма|about=доказательство оценки времени работы алгоритма в случае вещественных стоимостей|statement=Пусть <tex>k=VE(\lceil \log V + 1 \rceil)</tex>. Разобьем работу алгоритма на группы по <tex>k</tex> последовательных итераций. Утверждается, что каждая группа фиксирует поток на независимом ребре <tex>uv</tex>, то есть итерации из другой группы не меняют величину <tex>f(uv)</tex>.|proof=:Оценка времени работы следует непосредственно из этого утверждения. :Чтобы доказать его, рассмотрим некоторую группу итераций. Пусть <tex>f</tex> {{---}} поток до первой итерации, а <tex>f'</tex> {{---}} после последней итерации этой группы. Обозначим за <tex>\fracvarepsilon'^{p*}</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\textttvarepsilon'^{*}</tex>. Таким образом, поток на ребре <tex>uv</tex> не изменится при итерациях, происходящих после этой группы. Таким образом, по [[#theorem1|теореме]] каждая группа фиксирует поток на независимом ребре.}} ==Алгоритм поиска цикла минимального среднего веса=====Наивный способ===Устроим [[Вещественный двоичный поиск |двоичный поиск]].Установим нижнюю и верхнюю границы величины среднего веса цикла <tex>l</tex> и <tex>r</tex> соответственно, вычислим серединное значение <tex>m</tex> и отнимем полученную величину <tex>m</tex> от всех ребер сети. Если теперь в нашей сети есть отрицательный цикл (этот факт можно проверить при помощи [[Алгоритм Форда-Беллмана #Нахождение отрицательного цикла|алгоритма Форда-Беллмана]]), значит существует цикл с меньшим средним весом, чем <tex>m</tex>. Тогда продолжим поиск среди значений в диапазоне от <tex>l</tex> до <tex>m</tex>, иначе {{---}} от <tex>m</tex> до <tex>r</tex>. Тогда, если <tex>C_{max}</tex> и <tex>C_{min}</tex> {{---}} максимальная и минимальная возможные величины среднего веса цикла соответственно, такой алгоритм для вещественных значений весов ребер будет работать за <tex>O\left(\log \dfrac{C_{max}-C_{min}}{\varepsilon} \cdot EV\right)</tex>, где <tex>\varepsilon</tex> {{---}} точность выбора среднего веса цикла.При этом для целочисленных значений на ребрах точность выбора величины среднего веса цикла не может превысить <tex>\dfrac{1}{V}</tex>, что дает нам оценку <tex>O\left(\log (V(C_{max}-C_{lenmin})) \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>d[i][u]</tex> {{---}} длина минимального пути от <tex>s</tex> до <tex>u</tex> ровно из <tex>i</tex> ребер.Тогда длина оптимального цикла <tex>\mu^{*}</tex> минимального среднего веса вычисляется как <tex>\min\limits_{u} {\max\limits_{k} {\dfrac{d[n][u]-d[k][u]}{n-k}}}</tex>. Достаточно будет доказать это правило для <tex>\mu^{*}=0</tex>, так как для других <tex>\mu^{*}</tex> можно просто отнять эту величину от всех ребер и получить снова случай с <tex>\mu^{*}=0</tex>.

====Сам алгоритм====Рассмотрим некоторый поток <tex>f</tex>. Находим Чтобы найти цикл после построения матрицы <tex>Cd[k][u]</tex>, обладающий наименьшим средним весом. Если <tex>\mu (C) \geq 0</tex>запомним, то при каких <tex>fu</tex> {{---}} поток минимальной стоимости и алгоритм завершается.Иначе, отменим цикл <tex>Ck</tex>: достигается оптимальное значение <tex>f := f + c_{f}(C)\cdot f_mu^{C*}</tex>, где и, используя <tex>c_{f}(C)d[n][u]</tex> , поднимемся по указателям предков. Как только мы попадем в уже посещенную вершину {{---}} остаточная пропускная способность цикла <tex>C</tex>.Вернемся к началу алгоритмамы нашли цикл минимального среднего веса.

====Время работы алгоритма====Этот алгоритм работает за <tex>O(VE\cdot VE^{2}\log{V})</tex>, при этом<texref>O(VE)[[Алгоритм Форда-Беллмана #Сложность| Сложность алгоритма Форда-Беллмана]]</texref> времени тратится на поиск цикла минимального среднего веса.

===Алгоритм поиска цикла минимального среднего веса=======наивный способПсевдокод====Устроим двоичный поиск. '''func''' findMinCycle('''Graph''' G)установим нижнюю и верхнюю границы <texfont color="green">l</tex> и / вводим мнимую вершину <tex>rs</tex>, вычислим середину от которой проведём рёбра нулевого веса в каждую вершину графа<tex/font>m '''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>m</texfont> от всех ребер. Если теперь в нашем графе есть отрицательный цикл, значит существует цикл с меньшим средним весом, чем fordBellman(s) <texfont color="green">m</tex>. Тогда сдвигаем правую границу на / <tex>m</tex>, иначе {{---}} левую.длина оптимального цикла</font>Такой алгоритм будет работать за m = <tex>O(\textttmin\limits_{logu} {\fracmax\limits_{1k}{\varepsilon} \cdot EV</tex>((d[n][u] - d[k][u]) / (n - k)) <!-----<font color="green">//запомнив значения <tex>, где u</tex> и <tex>\varepsilonk</tex> {{, дающих оптимальный результат, найдём цикл</font>---------}} точность выбора величины среднего веса цикла.>====способ убрать <tex!----чуть не забыла про отступы, дура тупая----->\texttt{log} \frac{1}{\varepsilon}</tex> из оценки====

Добавим к нашему графу вершину <tex>s</tex> и ребра из нее во все остальные вершины==См.также==Рассмотрим алгоритм Форда-Беллмана и попросим его построить нам следущую квадратную матрицу:<code> d* [[iИспользование потенциалов Джонсона при поиске потока минимальной стоимости][u] // длина минимального пути от s до u ровно из i ребер</code>Тогда длина оптимального цикла <tex>\mu^{*}</tex> минимального среднего веса вычисляется как <tex>\min\limits_{u} {\max\limits_{k} {\frac{d[n][u]-d[kСведение задачи о назначениях к задаче о потоке минимальной стоимости][u]}{n-k}}}</tex>.

Почему это так? Грубо говоря, достаточно доказать для <tex>\mu^{*}=0</tex>, так как для других <tex>\mu^{*}=Примечания==<references/tex> можно просто отнять его величину от всех ребер и получить рассматриваемый случай.

---==Источники информации==как же найти сам циклЗапомним, при каких <tex>u<* [https://tex> и <tex>k<youtu.be/tex> достигается этот минимум, и, используя <tex>d[nbykbw7HovSo?t=4287 Лекция 14 | Дополнительные главы алгоритмов | Андрей Станкевич | CSC | Лекториум]* [u]<http://sirius.cs.put.poznan.pl/~inf84789/acm/tex>, по указателям предков поднимаемсяp873-goldberg.pdf A.V.Goldberg and R.E. Как только мы зациклимся Tarjan {{---}} мы нашли цикл минимального среднего весаFinding Minimum-Cost Circulations by Cancelling Negative Cycles (Journal of the Association for Computing Machinery. Vol. 36, No. 4. October 1989. pp. 873-886.)]*[https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-854j-advanced-algorithms-fall-2008/lecture-notes/lec4.pdf Lecture by M.X.Goemans on Goldberg-Tarjan Min-Cost Circulation Algorithm]