Изменения

Из доказанных выше фактов следует, что при добавлении потока вдоль кратчайшего пути в сети с корректными потенциалами не появляется ребер с отрицательным весом (однако сами потенциалы уже становятся некорректными). Но так как ребер отрицательного веса нет, то мы можем пустить алгоритм Дейкстры из <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>.

==Реализация==

}

}

==Асимптотика==