福特—富尔克森方法

福特—富尔克森方法（Ford–Fulkerson method）处理有向容量网络中的最大流问题。给定源点s、汇点t和非负边容量，流量不能超出容量，其他顶点还要满足流入等于流出的守恒条件。方法通常从零流开始，反复寻找还可以增加总流量的调整方案。

它首先构造当前流的残量网络，再找一条从s到t的增广路径。沿路所有残量容量的最小值是这次可增加的瓶颈量；按此数值更新各边后重新寻找路径。方法本身没有固定必须选哪条路，所以它是算法框架，不能把某种特定搜索策略的性能无条件归给整个框架。

参考：[1]

对于一条容量c、现有流量f的边，正向剩余容量为c－f，反向则有f的撤销余地。反向残量边并不宣称原网络真的有一条可运输的反向边，而是记录可以减少此前分配、为更好的整体方案腾出空间。若原图还包含反向实边，实现中须正确区分或合并相应残量贡献。

例如s→a、s→b、a→b、a→t、b→t的容量都为1。先沿s→a→b→t送出1后，看似两端的部分通道已满，但残量路径s→b→a→t仍可增广，其中b→a撤销a→b的旧流。最终改成s→a→t与s→b→t各送1，总流量达到2。只考虑原图正向空余边就会错过这一步。

参考：[1]

当残量网络中从s不能到达t时，取S为仍能从s到达的顶点集合。原网络从S指向外部的边都已饱和，否则还能继续到达；从外部流入S的相关流量也不能留下可用的反向通路。于是当前流值恰好等于这个割的容量。

任何可行流都不可能超过任意s—t割的容量。因此找到流值与某个割容量相等，就同时给出了最大流和最小割的证据。这解释了停止条件的正确性：不是“搜索过很多次所以大概够了”，而是残量可达性产生了一个与当前答案吻合的上界。

参考：[1]

若容量为整数且从零流出发，每次增广至少增加1。设最大流值为F，至多需要F次增广；每次以邻接表搜索和更新花O(V＋E)，得到O(F(V＋E))的常见界。这依赖数值F，而不是仅依赖其二进制位数，因此是伪多项式界。有理容量可统一缩放为整数来证明终止，但缩放后的数值可能很大。

对含无理容量的一般实数网络，某些选路序列可能无限增广，流值甚至收敛到非最优值。若改用广度优先搜索，总选残量网络中边数最少的增广路径，就得到通常所称的埃德蒙兹—卡普算法，其常见时间界为O(VE²)。这一多项式保证来自特定选路规则，而非任意福特—富尔克森执行。

参考：[2]