Изменения

Перейти к: навигация, поиск

Алгоритм отмены цикла минимального среднего веса

201 байт добавлено, 18:31, 20 марта 2018
→‎Продвинутый алгоритм
Этот алгоритм работает за <tex>O(VE)</tex> <ref>[[Алгоритм Форда-Беллмана #Сложность| Сложность алгоритма Форда-Беллмана]]</ref>.
<!----------====Псевдокод==== '''func''' findMinfindMinCycle: '''Node''' s '''whileEdge''' <tex>f</tex>e <tex>c</tex> = <tex>\mathrm{min} \muinsert(Cs)</tex> <font color="green">// добавляем мнимую вершину <tex>\mu(C)s</tex> {{---}} вес минимального циклаи проводим рёбра нулевого веса в каждую вершину графа</font> '''iffor''' u '''in''' <tex>G</tex> e.begin = s e.end = u e.weight = 0 fordBellman(s) <tex>\mu (C) ^{*} = \min\limits_{u} {\max\limits_{k} {\geqslant 0dfrac{d[n][u]-d[k][u]}{n-k}}}</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><!---------------->
==См. также==
I am dark black
693
правки
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/64510»

Навигация