福特-福尔克森是否有任何变体可以在边缘增加额外的“重量”尺寸？
我的意思是，某些边缘比其他边缘更理想，尽管存在所有可能性，但它会优先考虑理想边缘而不是不太理想的边缘。
据我所知，增加权重有两种常见的概括。
最小成本流
假设您对每条边都有一个权重，并且想要计算满足约束且成本最小的流。 （成本 = 权重总和 * 沿相关边流动的单位）
这个问题被称为最小成本流 http://en.wikipedia.org/wiki/Minimum-cost_flow_problem.
可以在 networkx 中找到一个名为最小成本流 http://networkx.github.io/documentation/latest/reference/generated/networkx.algorithms.flow.min_cost_flow.html#networkx.algorithms.flow.min_cost_flow.
这里有一个好的基于原始对偶方法。
我最喜欢的算法实际上是由 Fulkerson 本人于 1961 年发明的，称为失衡算法 http://web.eecs.umich.edu/~pettie/matching/Fulkerson-out-of-kilter-min-cost-flow.pdf.
最大流量最小成本
假设您确实想要最大流量，但想选择权重最小的流量。
这与第一种解释不同，因为最小成本流可能不会给出最大可能的流。例如，假设我们有一个单边 start->end，其约束条件是流量在 0 到 1 范围内，权重为 1。
min-cost-flow 的流量将为 0，而 max-flow-min-cost 的流量将为 1。
可以在 networkx 中找到一个实现，称为最大流量最小成本 http://networkx.github.io/documentation/latest/reference/generated/networkx.algorithms.flow.max_flow_min_cost.html.
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
