== Потенциал Джонсона Мотивация == При [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости|поиске потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]] нам требуется находить минимальный по стоимости поток из истока в сток. Поскольку стоимость некоторых рёбер может быть отрицательной, нам приходится использовать [[Алгоритм Форда-Беллмана|алгоритм Форда-Беллмана]] для поиска кратчайшего пути. Однако гораздо эффективней было бы применить [[Алгоритм Дейкстры|алгоритм Дейкстры]]. Для этого нам надо перевзвесить рёбра графа.
{{Определение
|definition=Пусть дана транспортная сеть <tex>\,G(V,E)</tex>. Введем в каждой вершине потенциал <tex>\,P_i</tex>. Тогда остаточная стоимость ребра <tex>\,C_{P_{ij}}</tex> определяется как
== Использование потенциалов Джонсона ==
Если Возьмём значения потенциалов в вершинах равными минимальному по цене расстоянию от стока до них, или <tex>+\infty</tex> если она недостижима. Так как <tex>\,C_{ij} + P_i</tex> это длина какого-то пути до вершины <tex>\forall i, j </tex>, а <tex>\,P_j</tex> - длина минимального пути, то <tex>C_{P_{ij}} \geqslant 0</tex> то при поиске минимального по стоимости пути , что от истока до стока можно пользоваться алгоритмом Дейкстры, а не алгоритмом нас и требовалось.Значения потенциалов найдём с помощью [[Алгоритм Форда-Беллмана|алгоритма Форда-Беллмана]]. Таким образом, что сильно улучшает ассимптотику нам его придётся запустить всего один раз, а не на каждом шаге алгоритма. ==Асимптотика==Обозначим время работы поиска кратчайшего пути <tex>F(V, E)</tex>.[[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости|Поиске потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]] работает за <tex>O(F(V, E) \cdot |f|)</tex>.Если использовать [[Алгоритм Дейкстры|алгоритм Дейкстры]] с Фиббоначевыми кучами, то <tex>F(V, E)= V log V + E</tex>. В результате получим время работы <tex>O((V log V + E) \cdot |f|)</tex>.
Пусть каждом шаге алгоритма значения потенциалов в вершинах будут равны минимальному по цене расстоянию от стока до них, или <tex>+\infty</tex> если она недостижима== См. Так как <tex>\,C_{ij} + P_i</tex> это длина какоготакже ==* [[Алгоритм Дейкстры]]* [[Алгоритм Форда-то пути до вершины <tex>\,j</tex>, а <tex>\,P_j</tex> - длина минимального пути, то <tex>C_{P_{ij}} \geqslant 0</tex>, что от нас и требовалось.Беллмана]]* [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]]* [[Алгоритм Джонсона]]
[[Категория: Задача о потоке минимальной стоимости]]
