关于Ford-Fulkerson算法中backward edges有效性及最大流计算逻辑的技术疑问

我来帮你拆解这两个绕人的问题，当年我啃Ford-Fulkerson的时候，也在反向边和最大流求和这两点上卡了好几天，完全懂你的困惑！

一、为什么带反向边的增广路，等价于原图中的可行调整？ #

首先得搞明白：残留网络里的反向边，不是原图里真实存在的边，它本质上是算法给的一个“反悔权”——代表“我之前给这条边分配了X单位流量，现在可以把其中一部分撤回来，重新分配给其他路径”。

举个最直观的例子：
假设我们有路径 s→A→t（A→t容量2），还有另一条路径 s→B→A→t（B→A容量3）。算法第一次瞎选了s→A→t，先流了2单位，这时候A→t的容量就用完了。如果没有反向边，算法会以为A到t没空间了，就不会考虑s→B→A→t这条路径，但实际上，我们可以把之前从A到t的2单位流量撤回来1单位，这样A→t就有1单位的空间，同时A可以接收B过来的3单位流量，最终总流量能到2（原来的）-1（撤回）+3（新流）=4，比之前的2大很多。

这个“撤回流量”的操作，就是靠残留网络里的反向边实现的——它允许算法在残留网络里走A←t这条反向边，本质上就是在原图里减少A→t的流量，这完全符合可行流的规则：减少流量不会违反容量限制，也不会打破中间节点的流量守恒（A少流1到t，就多1单位可以分给B→A的流量）。

换句话说，残留网络里带反向边的增广路，对应的是对当前流的一个合法调整方案，这个方案在原图里是完全可行的，不是算法凭空造出来的。

二、为什么所有增广路的流量之和就是最大流？ #

你可能会觉得：“为啥不直接找那些能一步到位的增广路，反而要把所有小增量加起来？”其实Ford-Fulkerson是个“贪心迭代”的思路——每次找到一条能增加流量的路径，就把流量加上去，直到再也找不到任何能增加流量的路径为止。

这里的关键是最大流最小割定理：当你找不到任何增广路的时候，当前的流就是最大流。这时候，你可以把图分成两个集合：所有从s能通过残留网络到达的节点（记为S），剩下的节点（记为T，包含t）。这个(S,T)就是一个“最小割”——把S和T分开的所有边的容量之和，就是当前流的大小，而根据定理，最大流就等于最小割的容量，所以此时的总流量就是最大的。

而每次找到的增广路，都是在给总流量加一个合法的小增量，这些增量加起来，最终就会达到最小割的容量，也就是最大流的数值。不管你找到的增广路是大是小，只要每次都能找到新的，就一直在靠近最大流，直到找不到为止。

备注：内容来源于stack exchange，提问作者Szyszka947