276
правок
Изменения
→Наивный способ
Устроим [[Вещественный двоичный поиск |двоичный поиск]].
Установим нижнюю и верхнюю границы величины среднего веса цикла <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>O\left(\texttt{log} \dfrac{1}{\varepsilon} \cdot EV\right)</tex>, где <tex>\varepsilon</tex> {{---}} точность выбора величины среднего веса цикла.
===Продвинутый алгоритм===
