5
правок
Изменения
Нет описания правки
== Использование потенциалов Джонсона ==
Возьмём значения потенциалов в вершинах равными минимальному по цене расстоянию от стока до них или <tex>+\infty</tex>, если она недостижима. Так как <tex>\,c_{ij} + p_i</tex> — это длина какого-то пути до вершины <tex>\,j</tex>, а <tex>\,p_j</tex> — длина минимального пути, то <tex>c_{p_{ij}} \geqslant 0</tex>, что от нас и требовалось.
Значения потенциалов найдём с помощью [[Алгоритм Форда-Беллмана|алгоритма Форда-Беллмана]]. Таким образом, нам его придётся запустить всего один раз, а не на каждом шаге алгоритма. Однако, после добавления потока вдоль кратчайшего увеличивающего пути в сети могут появиться новые ребра, равно как и исчезнуть старые, и будет необходимо пересчитать потенциалы, чтобы они оставались корректными, то есть <tex>p_v</tex> - длина кратчайшего пути от истока в вершину <tex>v</tex> в новой сети. Для начала докажем, что в сети с корректными потенциалами <tex>w_p(u, v) = 0</tex> для любого ребра <tex>(u, v)</tex>, лежащего на пути <tex>s \leadsto t</tex>.
==Реализация==
