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

Question

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

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

有趣的是，当我运行我的代码时，它给了我正确的结果。因此，我查看了Wikipedia 的示例，它专门展示了如何使用后端。当我将此图提供给我的代码时，我再次得到了正确答案。我还检查了结果流矩阵，它与维基百科的相同。

有人可以解释为什么我们必须添加和更新 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-7and 0-3-5-6-7。你得到 1 但 2 将是正确的答案。

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

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