我正在研究 Cormen 的“算法导论第 2 版”中的 Ford-Fulkerson 算法。它在有向图 G=(V, E) 的伪代码中描述如下，其中 f 是定义在 VxV 上的流
FORD-FULKERSON(G, s, t)
for each edge (u,v) in E(G)
do f[u, v] = 0
f[v, u] = 0
while there is a path p from s to t in the residual network Gf
do m = min{c(u, v)-f[u, v]: (u, v) is on p}
for each edge (u, v) on p
do f[u, v] = f[u, v] + m
f[v, u] = - f[u, v]
残差图 Gf 具有与 G 相同的顶点，并且具有那些有序对作为边 c(u, v) - f(u, v) > 0 的顶点 (u, v)。(编辑:c 是开始时给出的容量函数，并在不属于图形的边上扩展为零)
我不确定在“双向”存在边的情况下该怎么做，例如，当边及其反向在图中时算法会发生什么。我假设最小值中的 c(u, v) 是图中的原始容量。对于 (a, b) 和 (b, a) 都是边的情况，我是否需要以某种方式处理残差图中的四个边？目前在我的设置中我无法直接处理平行边。
我在 SO 上发现了以下问题:Maximum flow - Ford-Fulkerson: Undirected graph 但我不清楚结果是什么。
最佳答案
伪代码中没有任何关于图是循环的还是具有“反向边”的假设。只有边缘。
如果“两个方向”都有边，那么 c(u,v) 和 c(v,u) 将不同。 c(u,v) 只是从 u 到 v 的边的容量，而 c(v,u) 是从 v 到 u 的边的容量。它们彼此之间的关系并不比它们与任何其他边之间的关系更多。
换句话说，c(u,v) 和 f[u,v] 实际上都是边 上的函数，而不是顶点 上的函数。 (而且我认为如果这样写算法会更清晰。)因此将它们视为 c(E) 和 f[E]，其中 E 是一条边。 “残差网络”也是边的集合，而不是顶点。残差网络就是满足c(E) - f[E]为正的所有边。
该算法所做的全部工作是找到从源到目标仍然有一些空闲容量的任何路径，然后增加流量以消耗该空闲容量。 f[E] 是跨边的流量。因此，找到从 s 到 t 的所有 f[E] 都小于 c(E) 的任何路径，沿该路径取最小差值，并通过该差值增加沿该路径的流量。迭代直到没有路径剩余剩余容量。
如果 E 和 E' 恰好是两条彼此相反的边，则算法不关心；它将它们视为独立的边。
理解算法的作用是比较容易的部分。证明它收敛，证明它得到正确的答案，分析它的运行时间是困难的部分。
[更新]
啊，我明白了； f[u,v] 实际上是从 u 到 v 的流，而不是沿边的流(因为可能有两条边以相反的方向连接 u 和 v)。
我觉得f[u,v]基于顶点维护即可，但是cost graph和residual graph还是需要基于边。所以基本上完全按照算法所说的去做:对于路径上的每条边 E = (u,v)，找到 c(u,v)-f[u,v] 的最小值并相应地更新 f[] 值。然后根据原图的边计算出一个新的残差图；也就是说，对于每条边 E = (u,v)，如果 c(u,v) 大于 f[u,v] 则 E 是残差图的成员。
关于algorithm - 来自 Cormen 等人的 Ford Fulkerson，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/7741077/