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

Мотивация

При поиске потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости нам требуется находить минимальный по стоимости поток из истока в сток. Поскольку стоимость некоторых рёбер может быть отрицательной, нам приходится использовать алгоритм Форда-Беллмана для поиска кратчайшего пути. Однако гораздо эффективней было бы применить алгоритм Дейкстры. Для этого нам надо перевзвесить рёбра графа.

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

Пусть дана транспортная сеть [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]+\infty[/math] если она недостижима. Так как [math]\,C_{ij} + P_i[/math] это длина какого-то пути до вершины [math]\,j[/math], а [math]\,P_j[/math] - длина минимального пути, то [math]C_{P_{ij}} \geqslant 0[/math], что от нас и требовалось. Значения потенциалов найдём с помощью алгоритма Форда-Беллмана. Таким образом, нам его придётся запустить всего один раз, а не на каждом шаге алгоритма.

Асимптотика

Обозначим время работы поиска кратчайшего пути [math]F(V, E)[/math]. Поиске потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости работает за [math]O(F(V, E) \cdot |f|)[/math]. Если использовать алгоритм Дейкстры с Фиббоначевыми кучами, то [math]F(V, E)= V log V + E[/math]. В результате получим время работы [math]O((V log V + E) \cdot |f|)[/math].

См. также

• Алгоритм Дейкстры
• Алгоритм Форда-Беллмана
• Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости
• Алгоритм Джонсона