Изменения

Рассмотрим [[алгоритм Форда-Беллмана]] и попросим его построить нам следущую квадратную матрицусо следующим условием:<codetex> d[i][u] <// tex> {{---}} длина минимального пути от <tex>s </tex> до <tex>u </tex> ровно из <tex>i ребер</codetex>ребер.

Почему это так? Грубо говоря, достаточно доказать для Чтобы найти цикл после построения матрицы <tex>\mu^{*}=0d[k][u]</tex>, так как для других запомним, при каких <tex>\mu^{*}u</tex> можно просто отнять его величину от всех ребер и получить рассматриваемый случай.  ---как же найти сам циклЗапомним, при каких <tex>uk</tex> и достигается оптимальное значение <tex>k\mu^{*}</tex> достигается этот минимум, и, используя <tex>d[n][u]</tex>, поднимемся по указателям предков поднимаемся. Как только мы зациклимся попадем в уже посещенную вершину {{---}} мы нашли цикл минимального среднего веса.