6.5. Successive Shortest Paths

The strategy of the negative cycle cancelling algorithm was to compute an initial flow and then improve its cost by eliminating negative cycles until an optimal flow is obtained. The successive shortest paths algorithm takes a different approach. It starts with an optimal pseudo-flow. The algorithm then moves flow from nodes with positive excess to nodes with negative excess while maintaining optimality of the pseudo-flow until all nodes have excess \(0\). At this point, the resulting pseudo-flow is a flow and it is optimal.

As noted at the beginning of this chapter, this strategy is similar to preflow-push maximum flow algorithms. Those algorithms also started with an optimal preflow and then "drained" nodes with positive excess by pushing flow to their neighbours until the result was a flow, which was an optimal flow.

• It is far from clear what an "optimal" preflow or pseudo-flow is, given that the normal definition of an optimal solution is as a feasible solution with the best objective function value among all feasible solutions, but a preflow or pseudo-flow may not be feasible because it may violate flow conservation. Section 6.5.1 formalizes this notion of "optimality" of an infeasible solution and introduces the algorithmic paradigm on which both preflow-push algorithms and the successive shortest paths algorithm is based: the primal-dual-schema. This technique has been used to design a large number of exact and approximate optimization algorithms. In Sections 7.5.2 and 7.5.3, we discuss the Hungarian algorithm as another application of the primal-dual schema. In Chapter 12, we discuss how the primal-dual schema can be used to design approximation algorithms.

• Given the primal-dual schema, the successive shortest paths algorithm is then stated easily, and its proof of correctness and analysis are equally easy. We cover these in Section 6.5.2.