java - 福特-富尔克森实现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 的净流量大小相等且符号相反。

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

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

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

因此，通过从 A 向 B 推送“更多”，您必须减少从 B 向 A 推送的相应量。