1632
правки
Изменения
м
<!-----<font color="green">// добавляем мнимую вершину находим среднюю величину <tex>sm</tex> и проводим рёбра нулевого веса в каждую вершину графа</font>--------->
<!-----<font color="green">// добавляем мнимую вершину <tex>s</tex> и проводим рёбра нулевого вычитаем её из веса каждого ребра в каждую вершину графасети</font>--------->
<!-----<font color="green">// добавляем мнимую вершину <tex>s</tex> и проводим рёбра нулевого веса в каждую вершину графа</font>--------->
<!-----<font color="green">// добавляем мнимую вершину <tex>s</tex> и проводим рёбра нулевого веса в каждую вершину графа</font>--------->
<!----- <font color="green">// добавляем мнимую вершину если есть отрицательный цикл, то веса циклов находятся в диапазоне <tex>s[l;m]</tex> и проводим рёбра нулевого веса в каждую вершину графа // рассмотрим этот промежуток</font>--------->
<!-----<font color="green">// добавляем мнимую вершину <tex>s</tex> и проводим рёбра нулевого веса в каждую вершину графа</font>--------->
<!----- <font color="green">// добавляем мнимую вершину иначе запускаем двоичный поиск на отрезке <tex>s[m;r]</tex> и проводим рёбра нулевого веса в каждую вершину графа</font>--------->
<!-----<font color="green">// добавляем мнимую вершину <tex>s</tex> и проводим рёбра нулевого веса в каждую вершину графа</font>--------->
<!-----<font color="green">// добавляем вводим мнимую вершину <tex>s</tex> и проводим , от которой проведём рёбра нулевого веса в каждую вершину графа</font>--------->
<!-----<font color="green">// добавляем мнимую вершину <tex>s</tex> и проводим рёбра нулевого веса в каждую вершину графа</font>--------->
<!-----<font color="green">// добавляем мнимую вершину <tex>s</tex> и проводим рёбра нулевого веса в каждую вершину графа</font>--------->
<!-----<font color="green">// добавляем мнимую вершину <tex>s</tex> и проводим рёбра нулевого веса в каждую вершину графа</font>--------->
<!-----<font color="green">// добавляем мнимую вершину <tex>s</tex> и проводим рёбра нулевого веса в каждую вершину графа</font>--------->
<!-----<font color="green">// добавляем мнимую вершину <tex>s</tex> и проводим рёбра нулевого веса в каждую вершину графа</font>--------->
<!-----<font color="green">// добавляем мнимую вершину <tex>s</tex> и проводим рёбра нулевого веса в каждую вершину графа</font>--------->
<!-----<font color="green">// добавляем мнимую вершину <tex>s</tex> и проводим рёбра нулевого веса в каждую вершину графа</font>--------->
<!-----<font color="green">// добавляем мнимую вершину <tex>s</tex> и проводим рёбра нулевого веса в каждую вершину графа</font>--------->
<!-----<font color="green">// добавляем мнимую вершину <tex>s</tex> и проводим рёбра нулевого веса в каждую вершину графа</font>строим матрицу кратчайших расстояний, запустив алгоритм Форда---------> <!-----<font color="green">// добавляем мнимую вершину Беллмана из вершины <tex>s</tex> и проводим рёбра нулевого веса в каждую вершину графа</font>--------->
<!-----<font color="green">// добавляем мнимую вершину <tex>sm</tex> и проводим рёбра нулевого веса в каждую вершину графа{{---}} длина оптимального цикла</font>--------->
rollbackEdits.php mass rollback
'''func''' findMinCycleBinarySearch('''int''' l, '''int''' r)
m = (l + r) / 2
'''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))--->
findMinCycleBinarySearch (l, m)
'''else'''
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)
'''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++
fordBellman(s)
m = <tex>\min\limits_{u} {\max\limits_{k} }</tex>((d[n][u] - d[k][u]) / (n - k))
<!-----<font color="green">// добавляем мнимую вершину запомнив значения <tex>su</tex> и проводим рёбра нулевого веса в каждую вершину графа<tex>k</tex>, дающих оптимальный результат, найдём цикл</font>--------->
<!----чуть не забыла про отступы, дура тупая----->