容量与守恒共同限定可行流
标准单源单汇模型为有向边给定非负容量,每条边上的流量不得为负,也不得超过容量;除源点和汇点外,中间顶点流入与流出总量相等。目标是最大化离开源点的净流量,而不是简单把每条边都填满。
某些边即使还有剩余容量,也可能因下游瓶颈而无法承载更多流量。模型优化的是网络整体可行分配,不是单条最短路径的长度,也不要求所有流都沿同一条路径送达。多个商品、时间变化或额外费用需要另立模型。
反向残余边允许撤回旧分配
若一条容量c的边已经送出f,向前还可增加c减f;向后则可撤回至多f。这些可调整量组成残余网络。沿残余网络找到源到汇的增广路后,取路上最小残余量作瓶颈,统一调整整条路。
反向残余边不是凭空创造另一条实体运输通道,而是在算法中减少先前那条边的分配,把容量让给更好的整体组合。只寻找原图中从未使用的向前路径,可能错过需要先撤回部分旧安排才能得到的更大流。
无增广路与最小割形成证据
若残余网络里已没有源到汇的路径,从源仍可达的顶点与其余顶点形成一个割。可行流的值不超过任何源汇割的容量,而算法停止时这个割容量与当前流值相等,便共同证明当前流最大、该割最小。
寻找增广路的规则会影响计算成本,Princeton实现用广度优先搜索选择边数最少的增广路。数值实现还须处理舍入和溢出,不能把数学上的容量与守恒条件自动当作浮点运算永远精确。最大流值相同,也不要求每条边上的分配唯一。