Использование потенциалов Джонсона при поиске потока минимальной стоимости

Потенциал Джонсона

Определение:

Пусть дана транспортная сеть [math]\,G(V,E)[/math]. Введем в каждой вершине потенциал [math]\,P_i[/math]. Тогда остаточная стоимость ребра [math]\,C_{P_{ij}}[/math] определяется как [math]\,C_{P_{ij}} = C_{ij} + P_i - P_j [/math]

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

Использование потениалов Джонсона

Если [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], что от нас и требовалось.