问题描述
福特福克森(Ford-Fulkerson)是否有任何变型，使边缘增加了额外的重量"?
Is there any variation of the Ford-Fulkerson that adds an extra dimension of "weight" to the edges?
通过这种方式，我的意思是某些边缘比其他边缘更理想，尽管存在所有可能性，但它将优先考虑理想边缘而不是次要理想边缘.
By that, I mean some edges are more ideal than others, and while all the possibilities are there, it will prioritize the ideal edges over the lesser ideal edges.
推荐答案
我知道增加权重有两种常见的概括.
There are two common generalisations that I know of to add weights.
假设您对每个边都有权重，并且想要计算满足约束条件并具有最小成本的流. (成本=重量总和*沿关联边流动的单位)
Suppose you had a weight for each edge and wanted to compute the flow that satisfied the constraints and had minimum cost. (Cost = sum of weight * units flowing along associated edge)
此问题称为最低成本流.
可以在networkx中找到名为最低成本流.
An implementation can be found in networkx called min-cost-flow.
这是一个很好的 Topcoder教程原始对偶方法.
Here is a good topcoder tutorial on a primal-dual approach.
对此我最喜欢的算法实际上是Fulkerson于1961年发明的，称为更加有效的算法.
My favorite algorithm for this was actually invented by Fulkerson himself in 1961 and is called the out of kilter algorithm.
假设您确实想要最大流量，但想选择重量最小的流量.
Suppose you definitely wanted the maximum flow, but wanted to choose the flow with least weight.
这与第一种解释不同，因为最小成本流可能无法提供最大可能流.例如，假设我们有一个单边开始->结束，约束条件是流在0到1的范围内，权重为1.
This differs from the first interpretation, in that a min-cost-flow may not give the maximum possible flow. For example, suppose we have a single edge start->end with the constraint that the flow is in the range 0 to 1, and a weight of 1.
min-cost-flow将为0，而max-flow-min-cost将为1.
The min-cost-flow will be a flow of 0, while the max-flow-min-cost will have a flow of 1.
可以在称为 max_flow_min_cost .
这篇关于具有“加权"的Ford-Fulkerson算法.边缘的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！