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

Question

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

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

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

有人可以解释为什么我们必须添加和更新 back-edges，并举例说明它们很重要吗？

这是我编写的代码（更新为包括后边缘）：

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 将是正确的答案。

您是否插入了后边缘，然后您会找到以下路径：

1. 0-3-4-7
2. 0-1-2-4-3(back-edge!)-5-6-7，得到最大流量 2。