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

如果你可以沿着一个边缘沿任一方向推进一个流动，那么从A到B的净流量必须在大小上相等，从B到A的净流量在符号上是相反的。

就像在电路分析中一样:如果从A到B的电流为5安培，那么从B到A的电流为-5A。

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

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

因此，通过将“更多”从A推到B，你必须将从B推到A的数量减少一个相应的数量。

Answer 2

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

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