42
правки
Изменения
м
Нет описания правки
{{Определение
|definition=Пусть дана транспортная сеть <tex>\,G(V,E)</tex>. Введем в каждой вершине потенциал <tex>\,P_ip_i</tex>. Тогда остаточная стоимость ребра <tex>\,C_c_{P_p_{ij}}</tex> определяется как<tex>\,C_c_{P_p_{ij}} = C_c_{ij} + P_i p_i - P_j p_j </tex>
}}
Заметим, что сумма остаточных стоимостей ребер вдоль любого пути отличается от суммы стоимостей вдоль того же самого пути на разность между потенциалом первой и последней вершины.
== Использование потенциалов Джонсона ==
Возьмём значения потенциалов в вершинах равными минимальному по цене расстоянию от стока до них или <tex>+\infty</tex>, если она недостижима. Так как <tex>\,C_c_{ij} + P_ip_i</tex> — это длина какого-то пути до вершины <tex>\,j</tex>, а <tex>\,P_jp_j</tex> — длина минимального пути, то <tex>C_c_{P_p_{ij}} \geqslant 0</tex>, что от нас и требовалось.
Значения потенциалов найдём с помощью [[Алгоритм Форда-Беллмана|алгоритма Форда-Беллмана]]. Таким образом, нам его придётся запустить всего один раз, а не на каждом шаге алгоритма.
