Изменения
Нет описания правки
Такой алгоритм будет работать за <tex>O(\texttt{log} \frac{1}{\varepsilon} \cdot EV)</tex>, где <tex>\varepsilon</tex> {{---}} точность выбора величины среднего веса цикла.
====способ убрать <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^{*}</tex> можно просто отнять его величину от всех ребер и получить рассматриваемый случай.
---
как же найти сам цикл
Запомним, при каких <tex>u</tex> и <tex>k</tex> достигается этот минимум, и, используя <tex>d[n][u]</tex>, по указателям предков поднимаемся. Как только мы зациклимся {{---}} мы нашли цикл минимального среднего веса.
Этот алогоритм работает за <tex>O(VE)</tex>.
