693
правки
Изменения
→Псевдокод
Чтобы найти цикл после построения матрицы <tex>d[k][u]</tex>, запомним, при каких <tex>u</tex> и <tex>k</tex> достигается оптимальное значение <tex>\mu^{*}</tex>, и, используя <tex>d[n][u]</tex>, поднимемся по указателям предков. Как только мы попадем в уже посещенную вершину {{---}} мы нашли цикл минимального среднего веса.
Этот алогоритм алгоритм работает за <tex>O(VE)</tex> <ref>[[Алгоритм Форда-Беллмана #Сложность| Сложность алгоритма Форда-Беллмана]]</ref>. ====Псевдокод==== '''func''' cancel: '''while''' (true) c = <tex>\mathrm{min}_C(m(C))</tex> // m(C) {{---}} вес минимального цикла '''if''' m(C) <tex>\geqslant 0</tex> F = f // тогда f {{---}} поток минимальной стоимости '''else''' f += C(<tex>f_C</tex>) // иначе отменим цикл
==См. также==
