我正在尝试实现“ Beyond the Flow Decomposition Barrier , 1988”中描述的 Goldberg-Rao maxflow 算法。论文说我们正在寻找可接受弧上的流动。
The arc(vw) is admissible if distance(v) > distance(w) + length(vw).
要找到弧的长度，我们需要以下计算：
Initially, F = sum of capacities of all arc's leaving the source
lambda = min (num of nodes ^ 2/3 , num of arcs ^ 1/2)
Δ = F/lambda
length equals 0 on arcs with large residual capacities (res.cap >= 3Δ) and 1 otherwise
在算法计算期间，F 只能减小。所以，如果有大容量的弧，它们将永远不会被接受，我们将无法推动流通过它们。
在示例中 F = 5, lambda = 1.7, Δ = 3 - 所以从 2 到 T 的容量为 10 的弧是绝对不允许的。
有谁知道如何解决这个问题？以及弧的上限容量的限制究竟是如何改进最大流搜索的？
