A primal simplex algorithm that solves the maximum flow problem in at most nm pivots and O(n2m) time

The authors propose a primal network simplex algorithm for solving the maximum flow problem which chooses as the arc to enter the basis one that is closest to the source node from amongst all possible candidates. They prove that this algorithm requires at most nm pivots to solve a problem with n nodes and m arcs, and give implementations of it which run in O(n²m) time. The present algorithm is, as far as is known, the first strongly polynomial primal simplex algorithm for solving the maximum flow problem.