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: c = <tex>\mathrm{min}_C(m(C))</tex> // m(C) - вес минимального цикла '''if''' m(C) <tex>\geqslant 0</tex> min_f = f // тогда f - поток минимальной стоимости '''else''' f += C(f_C) // иначе отменим цикл
==См. также==
