42
правки
Изменения
→Использование потенциалов Джонсона
== Использование потенциалов Джонсона ==
Возьмём значения потенциалов в вершинах равными минимальному по цене расстоянию от стока до них или <tex>+\infty</tex>, если она недостижима. Так как <tex>\,C_{ij} + P_i</tex> - — это длина какого-то пути до вершины <tex>\,j</tex>, а <tex>\,P_j</tex> - — длина минимального пути, то <tex>C_{P_{ij}} \geqslant 0</tex>, что от нас и требовалось.
Значения потенциалов найдём с помощью [[Алгоритм Форда-Беллмана|алгоритма Форда-Беллмана]]. Таким образом, нам его придётся запустить всего один раз, а не на каждом шаге алгоритма.
