Изменения

:Рассмотрим [[Дополняющая сеть, дополняющий путь|остаточную сеть]] {{---}} граф <tex>G_{f}</tex>. В нем нет отрицательных циклов, так как <tex>f</tex> {{---}} поток минимальной стоимости<ref>[[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]]</ref>.  :Добавим вершину <tex>a</tex> и проведем из нее ребро стоимости <tex>0</tex> во все вершины графа <tex>G_{f}</tex>. В качестве <tex>\varphi(u)</tex> выберем стоимость минимального пути из <tex>a</tex> в <tex>u</tex>. :Рассмотрим теперь некоторое ребро <tex>uv</tex>. Понятно, что <tex>\varphi(v) \leqslant \varphi(u) + p(uv)</tex>. (Здесь сравниваются минимальный путь <tex>a \rightsquigarrow v</tex> и путь <tex>a \rightsquigarrow u \rightarrow v</tex>. Перенеся <tex>\varphi(v)</tex> в другую часть неравенства, получаем <tex>0 \leqslant \varphi(u) + p(uv) - \varphi(v)</tex>, что и требовалось доказать.}}