1632
правки
Изменения
м
rollbackEdits.php mass rollback
Из доказанных выше фактов следует, что при добавлении потока вдоль кратчайшего пути в сети с корректными потенциалами не появляется ребер с отрицательным весом (однако сами потенциалы уже становятся некорректными). Но так как ребер отрицательного веса нет, то мы можем пустить алгоритм Дейкстры из <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>f[e] \leftarrow 0</tex>
}
Запустим алгоритм Форда-Беллмана, в результате для каждой вершины: <tex>p[v] </tex> — кратчайшее расстояние <tex>s \leadsto ev</tex>,
если за длину ребра принимается его стоимость.
'''while''' (существует путь <tex>s \leadsto t</tex> в остаточной сети <tex>G_f</tex>) {
