我在理解用于查找最大流量的 Ford-Fulkerson 算法时遇到了一些麻烦，希望能得到一些帮助。
如果我们看下图，其中源 A 和汇 F 列出了每条边的边容量。
您会注意到节点 B 和 C 有一条双向边，BC 的容量为 8，CB 的容量为 3。
现在，假设找到的第一条路径是 ABCF，其中瓶颈容量为 8。因此，我们在创建此图的路径上推送 8 个流：
现在让我们说下一条路径是 ACBDF。
我的问题是我们现在能够通过 CB 推动多少流量？是 11 通过使用 8 个已经推送的流以及另一边的 3 个容量，还是只有 3 个或可能是 8 个？
感谢您的时间。
我认为您错误地构建了第二个残差图。这是我从第一张图中准备的版本。
每当您将流传递到增广路径时，您都需要随之调整容量。因此，当您沿路径 ABCF 传递值为 8 的流时，您需要在将下一个流传递到图中之前调整相关边的容量。
因此，值 8 来自边缘 BC 或 CF 的瓶颈容量。由于您已经在这两个边缘中通过了最大流量，并且您不能通过超过 8 个，因此您已经最大限度地利用了这些边缘的容量。这概括为这样一种想法，即每当您使用某些边传递一些流时，您需要绘制后向边，其中流值加上后向边的容量并从前向边中减去。
您可以从我的第二张图表版本中看到这一点。由于 BC 没有更多容量来承载额外的流量 (8 - 8 = 0)，我省略了边缘并将容量添加到反向边缘（即容量增加到 3 + 8 = 11 的 CB）。同样的事情也发生在 CF 身上。
现在对于 AB，因为我们已经通过了 8 以及容量为 10 的路径，我们仍然有 2 个容量来通过更多的流量。因此，我们从 AB 中减去该值并得到 (10 - 8 = 2)。我们还添加反向边 BA，它正在创建添加流量值（即 0 + 8 = 8）。
现在我们已经正确构建了残差图，剩下的唯一可以承载来自 AF 的流量的增广路径是 ABDF，流量值为 2（瓶颈容量为 2）。
因此最大流量值（总流量值）为 8 + 2 = 10
希望有帮助！