1

我正在尝试学习在 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/

4

2 回答 2

2

如果您可以沿边沿任一方向推动流量，则从 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 的数量减少相应的数量。

于 2016-04-14T08:22:51.577 回答