Ford-Fulkerson 实施 java

Question

我正在尝试学习在 java 中实现 Ford-Fulkersons 算法，并在互联网上找到了一些帮助，但我卡在了这段代码中

        // update residual capacities of the edges and
        // reverse edges along the path
        for (v=t; v != s; v=parent[v])
        {
            u = parent[v];
            rGraph[u][v] -= path_flow;
            rGraph[v][u] += path_flow;
        }

多亏了评论，我有点理解它是如何工作的，但不完全确定为什么需要它。为什么要减去？

来源：http://www.geeksforgeeks.org/ford-fulkerson-algorithm-for-maximum-flow-problem/

Answer 1

您可以参考 https://github.com/mission-peace/interview/blob/master/src/com/interview/graph/FordFulkerson.java

和视频 https://www.youtube.com/watch?v=GiN3jRdgxU4

Answer 2

如果您可以沿边沿任一方向推动流量，则从 A 到 B 的净流量必须与从 B 到 A 的净流量大小相等且符号相反。

就像在电路分析中一样：如果 5 安培的电流从 A 流向 B，则 -5A 的电流从 B 流向 A。

A     Resistor      B
O-----[======]------O
  5A ->

A     Resistor      B
O-----[======]------O
             <- -5A

因此，通过将 "more" 从 A 推送到 B，您必须减少从 B 推送到 A 的相应数量。