Hello. I've been trying to understand min cost max flow algorithm for several days and now I realised I don't understand why Jonhson's potentials work. We use them so that all edges have nonnegative weights. As I remember, Jonhson's algorithm works only if there aren't any cycles with negative weight. But isn't it the criteria for optimal MCMF, that there are no negative cycles in the residual network? So, until we actually find the optimal flow, we can't use potentials as there are negative cycles. Why can we use potentials then?