来自Cormen等人的Ford Fulkerson

Question

我正在研究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相同的顶点,并且具有作为边的那些有序的顶点对(u,v),其中c(u,v)-f(u,v)> 0.(编辑:c是容量函数在开始时给定并在边缘上扩展为零而不是图形的一部分)

我不确定在"双向"存在边缘的情况下该怎么做,例如当边缘及其反转在图中时算法中会发生什么.我假设最小的c(u,v)是图中的原始容量.在(a,b)和(b,a)都是边缘的情况下,我是否需要以某种方式处理残差图中的四条边？在我的设置中,我无法直接处理平行边缘.

我在SO上发现了以下问题: 最大流量 - Ford-Fulkerson:无向图 但我不清楚结果是什么.

Answer 1

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

如果"双向"存在边缘,则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],但是成本图和残差图仍然需要基于边.所以基本上完​​全按照算法所说的做法:对于路径上的每个边E =(u,v),找到c(u,v)-f [u,v]的最小值并相应地更新f []值.然后根据原始图的边缘计算新的残差图; 也就是说,对于每个边E =(u,v),如果c(u,v)大于f [u,v],则E是残差图的成员.