Изменения

При [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости|поиске потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]] нам требуется находить минимальный по стоимости поток из истока в сток. Это реализуется с помощью алгоритмов поиска кратчайшего пути в графе. Поскольку стоимость некоторых рёбер может быть отрицательной, нам приходится использовать [[Алгоритм Форда-Беллмана|алгоритм Форда-Беллмана]] для поиска кратчайшего пути. Однако гораздо эффективней было бы применить [[Алгоритм Дейкстры|алгоритм Дейкстры]]для этой же цели, так как у него гораздо лучше асимптотика. Для этого нам надо перевзвесить рёбра графа.

|definition=Пусть дана транспортная сеть <tex>\,G(V,E)</tex>, где <tex>V</tex> — множество вершин графа, а <tex>E</tex> — множество рёбер. Введем в каждой вершине потенциал <tex>\,p_i</tex>. Тогда остаточная стоимость ребра <tex>\,c_{p_{ij}}</tex> определяется как

Обозначим время работы поиска кратчайшего пути <tex>F(V, E)</tex>.[[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости|Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимостиМетод целиком]] работает за <tex>O(F(V, E) \cdot |f|)</tex>, где <tex>F(V, E)</tex> — время одной итерации. Время, затраченное на одну итерацию, определяется скоростью поиска кратчайшего пути.Если для этой цели использовать [[Алгоритм Дейкстры|алгоритм Дейкстры]] с Фиббоначевыми кучами, то поиск мы осуществим за <tex>FO(V, E)= V log V + E)</tex>.  Не стоит так же забывать, что для расчёта потенциалов мы один раз запустили Алгоритм Форда-Беллмана.В результате получим время работы <tex>O((V log V + E) \cdot |f| + V E)</tex>.

Это лучше, чем <tex>O((V E) \cdot |f|)</tex>, что получается при использовании [[Алгоритм Форда-Беллмана|алгоритма Форда-Беллмана]]для поиска кратчайшего пути на каждой итерации.