693
правки
Изменения
→Сложность
Для сетей с целочисленными стоимостями на ребрах <tex>O(VE\cdot VE\log{CV})</tex>, с вещественными {{---}} <tex>O(VE\cdot VE^{2}\log{V})</tex>.
В обоих случаях <tex>O(VE)</tex> времени тратится на поиск цикла минимального среднего веса.
===Псевдокод===
'''func''' findMin:
'''while''' <tex>f</tex>
<tex>c</tex> = <tex>\mathrm{min} \mu(C)</tex> <font color="green">// <tex>\mu(C)</tex> {{---}} вес минимального цикла</font>
'''if''' <tex>\mu (C) \geqslant 0</tex>
'''return''' <tex>f</tex> <font color="green">// тогда мы нашли f {{---}} поток минимальной стоимости, алгоритм завершается</font>
'''else'''
<tex>f</tex> += <tex>c_{f}(C)\cdot f_{C}</tex> <font color="green">// иначе отменим цикл</font>
===Корректность===
