
(I didn't read the article, but here's how the proof I know goes) Take any other solution X, subtract the solution Y obtained by our method from that solution. Since the total flow was the same, the result XY is a circulation in the residual network of flow Y. And since no negative cycle exists in that network, and that any circulation can be represented as a sum of cycles, the cost of the circulation is nonnegative, hence the cost of X is not less than the cost of Y. 