Balanced network flows. VII. Primal–dual algorithms

We discuss an adaptation of the famous primal–dual 1-matching algorithm to balanced network flows which can be viewed as a network flow description of capacitated matching problems. This method is endowed with a sophisticated start-up procedure which eventually makes the algorithm strongly polynomial. We apply the primal–dual algorithm to the shortest valid path problem with arbitrary arc lengths, and so end up with a new complexity bound for this problem.