Busacker Gowen algorithm

Contents

Also known as Roy's algorithm, Busacker Gowen's algorithm calculates a maximum flow at minimal cost.

The principle is simple, the search for the increasing path is done by a calculation of shortest way (lowest cost path). The optimality criteria are equivalent to the flow problem.

The algorithm is summarized as follows:

Build a graph of pcc (shortest path) from the flow deviation graph
- arc identical to the deviation graph
- price corresponding to the original arc if in the same direction, otherwise reverse
Look for a pcc from s to t
- if it exists, it is the increasing path, the saturated one and return to the previous step
- if there is no path, end of the algorithm.