Until recently, fast algorithms for the maximum flow problem have typically proceeded by constructing layered networks and establishing blocking flows in these networks. However, in recent years, new distance-directed algorithms have been suggested that do not construct layered networks but instead maintain a distance label with each node. The distance label of a node is a lower bound on the length of the shortest augmenting path from the node to the sink. In this article the authors develop two distance-directed augmenting path algorithms for the maximum flow problem. Both the algorithms run in O(n2m) time on networks with n nodes and m arcs. The authors also point out the relationship between the distance labels and layered networks. Using a scaling technique, they impove the complexity of the present distance-directed algorithms to O(nmlogU), where U denotes the largest arc capacity. The authors also consider applications of these algorithms to unit capacity maximum flow problems and a class of parametric maximum flow problems.
