10

我正在研究 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 但我不清楚结果是什么。

4

1 回答 1

5

伪代码中没有任何关于图是循环的还是具有“反向边缘”的假设。只有边缘。

如果在“两个方向”上都有边，则 c(u,v) 和 c(v,u) 将是不同的。c(u,v) 只是从 u 到 v 的边的容量，而 c(v,u) 是从 v 到 u 的边的容量。它们彼此之间的关系并不比它们与任何其他边缘的关系更多。

换句话说，c(u,v) 和 f[u,v] 实际上都是edges上的函数，而不是vertices。（而且我认为如果这样写算法会更清楚。）所以把它们想象成 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]，但是成本图和残差图仍然需要基于边。所以基本上完​​全按照算法所说的去做：对于路径上的每个边 E = (u,v)，找到 c(u,v)-f[u,v] 的最小值并相应地更新 f[] 值。然后根据原图的边计算一个新的残差图；也就是说，对于每条边 E = (u,v)，如果 c(u,v) 大于 f[u,v]，则 E 是残差图的成员。

于 2011-10-12T15:37:10.940 回答