Ford-Fulkerson 是否有任何变体为边缘增加了额外的“重量”维度？
我的意思是，有些边缘比其他边缘更理想，尽管存在所有可能性，但它会将理想边缘优先于不太理想的边缘。
问问题
1331 次
1 回答
3
我知道有两种常见的概括来添加权重。
最小成本流
假设您对每条边都有一个权重，并且想要计算满足约束且成本最低的流。（成本 = 重量总和 * 沿相关边流动的单位）
这个问题称为最小成本流。
可以在 networkx 中找到一个实现，称为min-cost-flow。
这是一个很好的关于原始对偶方法的顶级编码器教程。
我最喜欢的算法实际上是富尔克森本人在 1961 年发明的，被称为失衡算法。
最大流量最小成本
假设您确实想要最大流量，但想选择权重最小的流量。
这与第一种解释不同，因为最小成本流可能不会给出最大可能的流。例如，假设我们有一条单边 start->end，其约束条件是流在 0 到 1 的范围内，权重为 1。
min-cost-flow 的流量为 0，而 max-flow-min-cost 的流量为 1。
可以在 networkx 中找到一个实现，称为max_flow_min_cost。
于 2013-05-26T18:25:19.787 回答