276
правок
Изменения
→Продвинутый алгоритм
Добавим к нашему графу вершину <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} {\fracdfrac{d[n][u]-d[k][u]}{n-k}}}</tex>.
Достаточно будет доказать это правило для <tex>\mu^{*}=0</tex>, так как для других <tex>\mu^{*}</tex> можно просто отнять эту величину от всех ребер и получить снова случай с <tex>\mu^{*}=0</tex>.
