Busacker Gowen algorithm

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.

busacker gowen algorithm roy flow algorithm maximum minimum cost min cost flow