Busacker and Gowen algorithm

Also known as the algorithm name of Roy’s algorithm Busacker & Gowen calculates a maximum flow at minimum cost.

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

The algorithm is as follows:

  • To construct a shortest path from the flow residual graph
    • arc identical to the residual graph
    • price corresponding to the original arc if in the same direction, inverse otherwise
  • To find a shortest path from s to t
    • if it exists, it is the increasing path, saturated and return to the previous step
    • if there is no path, end of the algorithm.