什么是最小费用最大流问题

最小费用最大流同样建立在流网络上，可以看作最大流问题的一个拓展。不同的是，在最小费用最大流问题中，每条边同时包含三个属性，即最大流量，当前流量，该条边的费用。

求解最小费用最大流问题就是要求在一个流网络中求得一种状态，表示一种最大流的结果，并且在所有可能的最大流状态中，该最大流状态所使用的总费用最小。

求解步骤

求解最小费用最大流问题可通过以下步骤实现：

  • 初始化网络，对于所有当前已有负荷的边添加一条费用为该边相反数的反向边，对于当前负荷已达最大负荷的边，从边集合中删除。
  • 选取流网络中，从源节点到目的节点的一条最小费用路径。
  • 使用最大流问题中的Ford Fulkerson算法，求得该路径可以增加的负荷
  • 重新初始化该网络，继续寻找最小费用路径，知道流网络中不存在从源节点到目的节点的路径

通过这些步骤，便可求得一种最大流状态，且该最大流状态所用费用最小。