Ford-Fulkerson 是否有任何变体为边缘增加了额外的“重量”尺寸？
我的意思是，有些边缘比其他边缘更理想，尽管存在所有可能性，但它会将理想边缘优先于不太理想的边缘。
最佳答案
我知道有两种常见的概括来增加权重。
最小成本流
假设您对每条边都有一个权重，并且想要计算满足约束且成本最低的流。 (成本 = 权重之和 * 沿相关边流动的单位)
这个问题称为 minimum cost flow 。
可以在 networkx 中找到一个名为 min-cost-flow 的实现。
这是关于原始对偶方法的一个很好的 topcoder tutorial 。
我最喜欢的算法实际上是 Fulkerson 本人在 1961 年发明的，称为 out of kilter algorithm 。
最大流量最小成本
假设您肯定想要最大流量，但想要选择权重最小的流量。
这与第一种解释不同，因为最小成本流可能不会给出最大可能的流。例如，假设我们有一条边 start->end，约束条件是流在 0 到 1 的范围内，权重为 1。
min-cost-flow 的流量为 0，而 max-flow-min-cost 的流量为 1。
可以在 networkx 中找到一个名为 max_flow_min_cost 的实现。
关于php - 带有 "weighted"边的 Ford-Fulkerson 算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/16762231/