带“加权”边的Ford-Fulkerson算法

Question

是否有任何变种的福特-富尔克森，增加了额外的尺寸“重量”的边缘？

我的意思是，一些边比其他边更理想，虽然所有的可能性都在那里，但它将理想边优先于不太理想的边。

Answer 1

据我所知，有两种常见的方法来增加权重。

最小成本流

假设您对每条边都有一个权重，并希望计算满足约束并具有最小成本的流。(成本=沿着相关边流动的重量*单位的总和)

这个问题称为minimum cost flow。

在networkx中可以找到一个称为min-cost-flow的实现。

这是一个关于原始-对偶方法的很好的topcoder tutorial。

我最喜欢的算法实际上是由富尔克森本人在1961年发明的，被称为out of kilter algorithm。

最大流量最小成本

假设你确实想要最大的流量，但又想选择权重最小的流量。

这与第一种解释不同，因为最小费用流可能不会给出最大可能的流。例如，假设我们有一个单边start->end，约束条件是流在0到1的范围内，权重为1。

最小成本流将是流0，而最大流最小成本将具有流1。

在networkx中可以找到一个名为max_flow_min_cost的实现。