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.
Publicités
