Изменения

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

|definition=Пусть дана транспортная сеть <tex>\,G(V,E)</tex>, где <tex>V</tex> — множество вершин графа, а <tex>E</tex> — множество рёбер. Введем в каждой вершине потенциал <tex>\,P_ip(v)</tex>. Тогда остаточная потенциальный вес (то есть стоимость ) ребра <tex>\(u,C_{P_{ij}}v)</tex> определяется как<tex>\w_p(u,C_{P_{ij}} v) = C_{ij} w(u, v) + P_i p(u) - P_j p(v) </tex>

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

Возьмём значения потенциалов в вершинах равными минимальному по цене расстоянию от стока истока до них или , а расстояния найдём с помощью [[Алгоритм Форда-Беллмана|алгоритма Форда-Беллмана]]. Таким образом, нам его придётся запустить всего один раз, а не на каждом шаге алгоритма. Однако, после добавления потока вдоль кратчайшего увеличивающего пути в сети могут появиться новые ребра, равно как и исчезнуть старые, и будет необходимо пересчитать потенциалы, чтобы они оставались корректными, то есть <tex>p(v)</tex> - длина кратчайшего пути от истока в вершину <tex>v</tex> в новой сети. Научимся делать это, не запуская каждый раз Форда-Беллмана. Для начала докажем, что в сети с корректными потенциалами <tex>w_p(u, v) = 0</tex> для любого ребра <tex>(u, v)</tex>, лежащего на кратчайшем пути из <tex>s</tex> в <tex>t</tex>. Пусть <tex>+s, v_1, v_2, \inftyldots, v_k, t</tex> - кратчайший путь из <tex>s</tex> в <tex>t</tex>, если она недостижимаи <tex>d(u, v)</tex> - длина кратчайшего пути между вершинами <tex>u</tex> и <tex>v</tex> в исходной сети без потенциалов. Так как Тогда <tex>w(s, v_1) + w(v_1, v_2) + \ldots + w(v_k, t) = d(s, t)</tex> и <tex>w_p(s, v_1) + w_p(v_1, v_2) + \ldots + w_p(v_k,C_{ij} t) = p(s) + P_iw(s, v_1) + w(v_1, v_2) + \ldots + w(v_k, t) - p(t) = p(s) + d(s, t) - p(t) = p(s) + p(t) - p(t) = p(s) = 0</tex> — это длина какого-то . Таким образом, сумма всех потенциальных весов ребер на кратчайшем пути до вершины из <tex>s</tex> в <tex>t</tex> равна нулю. Кроме того, для любого ребра <tex>(u, v)</tex> <tex>w_p(u, v) \geq 0</tex>. Следственно,j<tex>w_p(u, v) = 0</tex>для любого ребра <tex>(u, а v)</tex>\,P_jлежащего на кратчайшем пути из <tex>s</tex> в <tex>t</tex> — длина минимального .  Более того, потенциальный вес всех ребер, обратных ребрам из кратчайшего пути, то тоже равен <tex>0</tex>. И правда, <tex>w_p(u, v) = w(u, v) + d(s, u) - d(s, v) = 0</tex>. Умножив на <tex>-1</tex>, получаем <tex>C_{P_{ij}} \geqslant 0= -w(u, v) - d(s, u) + d(s, v) = w(v, u) + d(s, v) - d(s, u) = w_p(v, u)</tex> Из доказанных выше фактов следует, что от нас и требовалосьпри добавлении потока вдоль кратчайшего пути в сети с корректными потенциалами не появляется ребер с отрицательным весом (однако сами потенциалы уже становятся некорректными). Но так как ребер отрицательного веса нет, то мы можем пустить алгоритм Дейкстры из <tex>s</tex>, чтобы насчитать новые потенциалы.Значения потенциалов найдём Пусть <tex>d_1(u, v)</tex> - кратчайшее расстояние, найденное алгоритмом Дейкстры, из <tex>u</tex> в <tex>v</tex> в сети с помощью [[Алгоритм Фордапоявившимися новыми ребрами, но старыми потенциалами, а <tex>d(u, v)</tex> -Беллмана|алгоритма Фордакратчайшее расстояние в новой сети без потенциалов. Нетрудно заметить, что <tex>d_1(s, v) = d(s, v) -Беллмана]]p(v)</tex>, следственно, <tex>d(s, v) = d_1(s, v) + p(v)</tex>. Зная настоящие расстояния от истока до каждой вершины, мы теперь можем проставить новые потенциалы. Таким образомДля каждой вершины <tex>v</tex> <tex>p(v) \gets d(s, v) = d_1(s, нам его придётся запустить всего один разv) + p(v)</tex>. Кроме того, мы также нашли новый кратчайший путь из истока из сток - а не значит, на каждом шаге следующей итерации алгоритмамы можем пустить поток по нему и повторить все заново.

Запустим алгоритм Форда-Беллмана, в результате для каждой вершины: <tex>p[v] </tex> — кратчайшее расстояние <tex>s \leadsto ev</tex>,

Восстановить <tex>P \leftarrow</tex> — кратчайший в смысле стоимости путь <tex>s \leadsto t</tex>, найденный на предыдущем шаге

Обозначим время работы поиска кратчайшего пути <tex>F(V, E)</tex>.[[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости|Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимостиМетод целиком]] работает за <tex>O(F(V, E) \cdot |f|)</tex>, где <tex>F(V, E)</tex> — время одной итерации. Время, затраченное на одну итерацию, определяется скоростью поиска кратчайшего пути.Если для этой цели использовать [[Алгоритм Дейкстры|алгоритм Дейкстры]] с Фиббоначевыми кучами, то поиск мы осуществим за <tex>FO(V, E)= V \log V + E)</tex>.  Не стоит так же забывать, что для расчёта потенциалов мы один раз запустили Алгоритм Форда-Беллмана.В результате получим время работы <tex>O((V \log V + E) \cdot |f| + V E)</tex>.  Это лучше, чем <tex>O((V E) \cdot |f|)</tex>, что получается при использовании [[Алгоритм Форда-Беллмана|алгоритма Форда-Беллмана]] для поиска кратчайшего пути на каждой итерации. 

Это лучшеВ применении к [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости|задаче о назначениях]]: пусть у нас есть <tex>N</tex> назначений. Построим специальным образом граф. Искомый поток в нём имеет имеет мощность <tex>N</tex>. Количество вершин — <tex>O(N)</tex>, чем рёбер — <tex>O(N^2)</tex>. Итого получаем асимптотику <tex>O(V EN^2 \log N + 2N^3) \cdot |f|= O(N^3)</tex>, что получается при использовании [[Алгоритм Форда-Беллмана|алгоритма Форда-Беллмана]].