A computational comparison of the Dinic and network simplex methods for maximum flow

The authors study the implementation of two fundamentally different algorithms for solving the maximum flow problem: Dinic’s method and the network simplex method. For the former, they present the design of a storage-efficient implementation. For the latter, the authors develop a ‘steepest-edge’ pivot selection criterion that is easy to include in an existing network simplex implementation. They compare the computational efficiency of these two methods on a personal computer with a set of generated problems of up to 4600 nodes and 27000 arcs.