(Alternative Construction of a Basic Feasible Flow Vector) Consider the following algorithm that tries to construct a flow vector that has a given divergence vector s, and is zero on arcs which are...

(Alternative Construction of a Basic Feasible Flow Vector) Consider the following algorithm that tries to construct a flow vector that has a given divergence vector s, and is zero on arcs which are not in a given spanning tree T. For any vector x, define the surplus of each node i by

The algorithm is initialized with x = 0. The typical iteration starts with a flow vector x and produces another flow vector x that differs from x along a simple path consisting of arcs of T. It operates as follows: a node i with gi > 0 and a node j with gj