Изменения
Нет описания правки
== Потенциал Джонсона ==
{{Определение
|definition=Пусть дана транспортная сеть <mathtex>\,G(V,E)</mathtex>. Введем в каждой вершине потенциал <mathtex>\,P_i</mathtex>. Тогда остаточная стоимость ребра <mathtex>\,C_{P_{ij}}</mathtex> определяется как<mathtex>\,C_{P_{ij}} = C_{ij} + P_i - P_j </mathtex>
}}
Заметим что сумма остаточных стоимостей ребер вдоль любого пути отличается от суммы стоимостей вдоль того же самого пути на разность между потенциалом первой и последней вершины.
== Использование потенциалов Джонсона ==
Если <mathtex>\forall i, j \,C_{P_{ij}} \geqslant 0</mathtex> то при поиске минимального по стоимости пути от истока до стока можно пользоваться алгоритмом Дейкстры, а не алгоритмом Форда-Беллмана, что сильно улучшает ассимптотику алгоритма.
Пусть каждом шаге алгоритма значения потенциалов в вершинах будут равны минимальному по цене расстоянию от стока до них, или <mathtex>+\infty</mathtex> если она недостижима. Так как <mathtex>\,C_{ij} + P_i</mathtex> это длина какого-то пути до вершины <mathtex>\,j</mathtex>, а <mathtex>\,P_j</mathtex> - длина минимального пути, то <mathtex>C_{P_{ij}} \geqslant 0</mathtex>, что от нас и требовалось.
