Изменения

Заметим что сумма остаточных стоимостей ребер вдоль любого пути отличается от суммы стоимостей вдоль того же самого пути на разность между потенциалом первой и последней вершины.

Если <math>\forall i, j \,C_{P_{ij}} \geqslant 0</math> то при поиске минимального по стоимости пути от истока до стока можно пользоваться алгоритмом Дейкстры, а не алгоритмом Форда-Беллмана, что сильно улучшает ассимптотику алгоритма.

Пусть каждом шаге алгоритма значения потенциалов в вершинах будут равны минимальному по цене расстоянию от стока до них, или <math>+\infty</math> если она недостижима. Так как <math>\,C_{ij} + P_i</math> это длина какого-то пути до вершины <math>\,j</math>, а <math>\,P_j</math> - длина минимального пути, то <math>C_{P_{ij}} \geqslant 0</math>, что от нас и требовалось.