693
правки
Изменения
→Продвинутый алгоритм
===Псевдокод===
'''funcEdge[]''' findMin:('''Graph''' G) '''while''' <tex>f</tex> <tex>c</tex> = <tex>\mathrm{min} \mu(C)</tex> <font color="green">// <tex>\muнайдём M(C)</tex> {{---}} вес минимального цикла</font> '''if''' C = c : M(c) = <tex>\mu (C) min\geqslant 0limits_c</tex>M(c) '''returnif''' M(C) <tex>f\geqslant</tex> 0 <font color="green">// тогда Если величина M(C) положительна, то мы нашли f {{---}} поток минимальной стоимости, на этом алгоритм завершается</font> '''return''' f '''else''' <tex>f</tex> += <tex>c_{f}(C)\cdot f_{C}</tex> <font color="green">// иначе отменим в противном случае отменяем цикл</font> f += c_f * f(C)
===Корректность===
====Псевдокод====
===Продвинутый алгоритм===
Добавим к нашему графу вершину <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: ('''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> {{*---} } длина оптимального цикла</font> 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>---------> <!----чуть не забыла про отступы, дура тупая----->
==См. также==