Busacker Gowen algorithm
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.