1632
правки
Изменения
м
<font color="green">// добавляем мнимую вершину <tex>s</tex> и проводим рёбра нулевого веса в каждую вершину графа</font>
rollbackEdits.php mass rollback
'''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>.
====Псевдокод====
'''func''' findMinCycle('''Graph''' G)
<font color="green">// вводим мнимую вершину <tex>s</tex>, от которой проведём рёбра нулевого веса в каждую вершину графа</font>
'''Node''' s
'''Edge[]''' e
insert(s)
i = 0
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>---------> <!----чуть не забыла про отступы, дура тупая----->
==См. также==
