Изменения

'''funcEdge[]''' findMin:('''Graph''' G) '''while''' f <tex>C</tex> = <tex>c</tex> : <tex>\mu(C) </tex>= <tex>\min\limits_c\mu(c)</tex> <font color="green">// <tex>\muнайдём M(C)</tex> {{---}} вес минимального цикла</font> C = c : M(c) = <tex>\min\limits_c</tex> M(c) '''if''' M (C)<tex>\geqslant 0</tex>0 '''return''' f <font color="green">// тогда Если величина M(C) положительна, то мы нашли f {{---}} поток минимальной стоимости, на этом алгоритм завершается</font> '''return''' f '''else''' f += <tex>c_{f}(C)\cdot f_{C}</tex> <font color="green">// иначе отменим в противном случае отменяем цикл</font> f += c_f * f(C)

'''func''' findMinCycleBinarySearch ('''int''' l, '''int''' r): <font color="green">// находим среднюю величину <tex>m</tex></font> m = (l + r) / 2 <texfont color="green">2// вычитаем её из веса каждого ребра в сети</texfont> '''for''' e : '''in''' edges e.weight -= m '''while''' l > r - 1 <!-----<font color="green">// добавляем мнимую вершину <tex>s</tex> и проводим рёбра нулевого веса в каждую вершину графа</font>---------> '''if''' <tex>\exists C</tex> C : <tex>\mu 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> и ребра рёбра из нее неё во все остальные вершины.

'''func''' findMinCycle: ('''NodeGraph''' sG) '''Edge''' e insert(s) <font color="green">// добавляем вводим мнимую вершину <tex>s</tex> и проводим , от которой проведём рёбра нулевого веса в каждую вершину графа</font> '''Node''' s '''Edge[]''' e insert(s) i = 0 '''for''' u '''in''' <tex>G</tex> e[i].begin = s e[i].end = u e[i].weight = 0 i++ <font color="green">// строим матрицу кратчайших расстояний, запустив алгоритм Форда-Беллмана из вершины <tex>0s</tex></font> fordBellman(s) <font color="green">// <tex>\mu^m</tex> {{*---}} длина оптимального цикла</texfont> m = <tex>\min\limits_{u} {\max\limits_{k} {\dfrac{}</tex>((d[n][u]-d[k][u]}{) / (n-k}}})) <!-----<font color="green">// запомнив значения <tex>u</tex> и <tex>k</tex>, дающих оптимальный результат, найдём цикл</font>---------> <!----чуть не забыла про отступы, дура тупая----->