为什么必须在Edmonds

为什么必须在Edmonds-Karp最大流量中考虑后沿？(Why must back-edges be taken into account in Edmonds-Karp Maximum Flow?)

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

我没有遍历残差图中的所有边，而是使用邻接列表遍历了原始图中存在的边。 用min flow更新残差图时，我没有更新任何后沿。

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

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

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

I was trying to implement Edmonds-Karp in C++ for maximum flow, and I wrote it slightly differently:

Instead of going through all edges in residual graph, I only went through the edges that are present in the original graph, using the adjacency list. I did not update any back-edges when updating the residual graph with min flow.

Interestingly, when I ran my code, it gave me correct results. So I went to Wikipedia's example, where it specifically show how a back-edge is being used. When I fed this graph to my code, I got the correct answer again. I also checked the resultant flow matrix, and it was identical to Wikipedia's.

Can someone explain why we must add and update back-edges, and maybe give an example where they are critical?

Here's the code that I wrote (updated to include back edges):

最满意答案

考虑以下流量网络

假设第一个流是s→u→v→t 。 （如果你反对Edmonds-Karp的BFS永远不会选择这个，那么用s和v之间以及u和t之间的一些顶点来增加图形）。

没有逆流u→v ，就不可能获得20的最佳流量。

Consider the following flow network

Suppose the first flow is s → u → v → t. (If you object that that the BFS of Edmonds-Karp would never choose this, then augment the graph with some more vertices between s and v and between u and t).

Without reversing flow u → v, it is impossible to obtain the optimal flow of 20.