Изменения

Алгоритм Форда-Беллмана работает за <tex>O(VE)</tex>. Нахождение максимального потока и , улучшение цикла работает за <tex>O(E)</tex>. Если обозначить максимальную стоимость потока как <tex>C</tex>, а максимальную пропускную способность как <tex>U</tex>, то алгоритм совершит <tex>O(ECU)</tex> итераций поиска цикла, если каждое улучшение цикла будет улучшать его на 1. В итоге имеем <tex>O(V E^2C U + maxFlow)</tex>, где <tex>maxFlow</tex> - асимптотика поиска максимального потока.