276
правок
Изменения
→Алгоритм
Приведенный алгоритм основан на идее [[Поток минимальной стоимости #Метод устранения отрицательных циклов в остаточной сети|алгоритма Клейна отмены цикла отрицательного веса]]. Выбор цикла минимального среднего веса вместо случайного делает алгоритм сильно полиномиальным.
{{Определение
|definition='''Сильно полиномиальными''' (англ. ''strongly polynomial'') в контексте данной задачи называются алгоритмы, чья сложность полиномиально зависит от <tex>V</tex> и <tex>E</tex>.}}
===Описание===
Обозначим как <tex>c_{f}(C)</tex> остаточную [[Определение сети, потока|пропускную способность]] цикла <tex>C</tex> при протекании в сети потока <tex>f</tex>.
Cтоимость цикла <tex>C</tex> обозначим за <tex>p(C)</tex>, а длину (число входящих в него ребер) {{---}} за <tex>\texttt{len}(C)</tex>.
{{Определение
|definition='''Средним весом цикла''' (англ. ''mean weight'') цикла будем называть отношение его стоимости к его длине <tex>\mu (C)=\dfrac{p(C)}{\texttt{len}(C)}</tex>}}
* '''Шаг1'''. Рассмотрим некоторый поток <tex>f</tex>.
* '''Шаг2'''. Найдем цикл <tex>C</tex>, обладающий наименьшим средним весом. Если <tex>\mu (C) \geqslant 0</tex>, то <tex>f</tex> {{---}} поток минимальной стоимости и алгоритм завершается.
