23-算法设计

7.4.2　算法设计

求解最小费用最大流有两种思路：

（1）先找最小费用路，在该路径上增流，增加到最大流，称为 最小费用路算法 。

（2）先找最大流，然后找负费用圈，消减费用，减少到最小费用，称为 消圈算法 。

最小费用路算法，是在残余网络上寻找从源点到汇点的最小费用路，即从源点到汇点的以单位费用为权的最短路，然后沿着最小费用路增流，直到找不到最小费用路为止。是不是有点像最短增广路算法？

最短增广路算法中求最短增广路是去权值的最短路，而最小费用路是以单位费用为权值的最短路。