322
правки
Изменения
Нет описания правки
Время, затраченное на одну итерацию, определяется скоростью поиска кратчайшего пути.
Если для этой цели использовать [[Алгоритм Дейкстры|алгоритм Дейкстры]] с Фиббоначевыми кучами, то поиск мы осуществим за <tex>O(V \log V + E)</tex>.
Не стоит так же забывать, что для расчёта потенциалов мы один раз запустили Алгоритм Форда-Беллмана.
В результате получим время работы <tex>O((V \log V + E) \cdot |f| + V E)</tex>.
Это лучше, чем <tex>O((V E) \cdot |f|)</tex>, что получается при использовании [[Алгоритм Форда-Беллмана|алгоритма Форда-Беллмана]] для поиска кратчайшего пути на каждой итерации.
В применении к задаче [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости|задаче о назначениях]]: пусть у нас есть <tex>N</tex> назначений. Построим специальным образом граф. Искомый поток в нём имеет имеет мощность <tex>N</tex>. Количество вершин — <tex>O(N)</tex>, рёбер — <tex>O(N^2)</tex>. Итого получаем асимптотику <tex>O(N^2 \log N + 2N^3) = O(N^3)</tex>.
== Литература ==
