php – 具有“加权”边缘的Ford-Fulkerson算法

Ford-Fulkerson是否有任何变化,为边缘增加了额外的“重量”尺寸？

通过这种方式,我的意思是一些边缘比其他边缘更理想,虽然所有可能性都在那里,但它将优先考虑理想边缘而不是较小的理想边缘.

解决方法:

我知道增加权重有两种常见的概括.

最低成本流量

假设您对每条边都有一个权重,并且想要计算满足约束并且成本最低的流量. (成本=重量总和*沿相关边缘流动的单位)

这个问题叫做minimum cost flow.

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

这是一个关于原始对偶方法的良好topcoder tutorial.

我最喜欢的算法实际上是由Fulkerson自己在1961年发明的,被称为out of kilter algorithm.

最@R_58_403@最小成本

假设你肯定想要最@R_58_403@,但想选择重量最轻的流量.

这与第一种解释的不同之处在于,最小成本流量可能无法提供最大可能的流量.例如,假设我们有一个单一的边开始 – >结束,其约束是流量在0到1的范围内,权重为1.

最小成本流量为0流量,而最@R_58_403@最小成本流量为1.

可以在名为max_flow_min_cost的networkx中找到此实现.

（编辑：北几岛）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!