6.6.2.1. Maintenance of Bounded Excesses

That the algorithm maintains Invariant 6.24 is easy to see:

At the beginning of the algorithm, we set \(f_e = 0\) for every edge \(e \in G\) and \(\pi_x = 0\) for every vertex \(x \in G\), just as in the successive shortest paths algorithm. Thus, every vertex has excess \(e_x = b_x \in [-U, U]\). Since \(\Delta = 2^{\lfloor \lg U\rfloor}\) in the first phase, we have \(U < 2\Delta\), that is, every vertex has excess strictly between \(-2\Delta\) and \(2\Delta\), and Invariant 6.24 holds at the beginning of the first phase.

Each \(\Delta\)-phase continues until there is either no excess vertex with excess at least \(\Delta\) or there is no deficit vertex with deficit at least \(\Delta\) (excess at most \(-\Delta\)). This explicitly ensures that Invariant 6.24 holds at the end of the \(\Delta\)-phase and thus also at the beginning of the \(\frac{\Delta}{2}\)-phase if \(\Delta > 1\).