693
правки
Изменения
→Наивный способ
Тогда, если <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_{min})) \cdot EV\right)</tex>.
====Псевдокод====
'''func''' findMinCycleBinarySearch (l, r):
m = (l + r) / 2
'''for''' e : edges
e.weight -= m
'''if'''<tex>\exists<tex> отрицательный цикл
findMinCycleBinarySearch (l, m)
'''else'''
findMinCycleBinarySearch (m, r)
===Продвинутый алгоритм===
