为什么在 Edmonds-Karp 最大流量中必须考虑后缘？

Question

我试图在 C++ 中实现 Edmonds-Karp 以获得最大流量，但我的写法略有不同：

我没有遍历残差图中的所有边，而是使用邻接表只遍历了原始图中存在的边。
我在用最小流量更新残差图时没有更新任何后边。

有趣的是，当我运行我的代码时，它给了我正确的结果。所以我去了 Wikipedia's example，它 专门展示了如何使用后缘 。当我将这张图输入我的代码时，我又得到了正确答案。我还检查了 结果流矩阵 ，它与维基百科的相同。

有人可以解释为什么我们必须添加和更新后缘，并可能举一个例子说明它们是关键的吗？

Here 是我编写的代码（已更新以包括后缘）：

Answer 1

考虑下面的流网络

假设第一个流程是s → u → v → t。（如果你反对 Edmonds-Karp 的 BFS 永远不会选择这个，那么在 s 和 v 之间用更多的顶点扩充图和在 u 和 t 之间。

没有逆流u → v，无法得到20的最优流

Answer 2

尝试以下案例：

int main() {
    Digraph<int> g(8);
    g.addEdge(0,1,1);
    g.addEdge(1,2,1);
    g.addEdge(2,4,1);
    g.addEdge(0,3,1);
    g.addEdge(3,4,1);
    g.addEdge(4,7,1);
    g.addEdge(3,5,1);
    g.addEdge(5,6,1);
    g.addEdge(6,7,1);

    cout<<g.maxFlowEdmondsKarp(0,7);

    return 0;
}

可视化：

你的程序先走最短的路0-3-4-7，然后没有机会找到0-1-2-4-7和0-3-5-6-7。你得到 1，但 2 是正确答案。

如果你插入了后缘，那么你会发现以下路径：

0-3-4-7
0-1-2-4-3(back-edge!)-5-6-7,获取最大流量2.

为什么在 Edmonds-Karp 最大流量中必须考虑后缘？

Why must back-edges be taken into account in Edmonds-Karp Maximum Flow?

c++

algorithm

graph

ford-fulkerson

edmonds-karp