二、最大流的求法
求网络图的最大流一般采用福特-佛劳克森（Ford-Fulkerson）算法，福特-佛劳克森算法的思想是通过标号的方法寻找从源到汇是否有流量可以增加的路线（这样的路线简称为增广链），如果有增广链，则调整增广链上弧的流量，来获得流值更大的流，直到找到最大流为止.
根据增广链的定义，在网络图中找增广链时，应该满足如下条件：（1）与前进方向一致的弧（简称前向弧）为非饱和弧；
（2）与前进方向相反的弧（简称后向弧）为非零流弧的路线.
例1 找出图9-38中从vs到vt的增广链.
图9-38
解 在图9-39中，从vs到vt的路线vs→v2→v5→v1→v4→vt，就是一条增广链.因为它的前向弧vs→v2，v2→v5，v1→v4，v4→vt，都是非饱和弧，而后向弧v5→v1是非零流弧.由于除此以外，再也找不到其他类似的路线，因此，在此网络图中，再也找不到其他增广链（由增广链的定义知，此路线为该网络图中唯一的增广链）.
调整增广链流量的方法：
（1）找到其上每条弧的可调整流量值，其中前向弧的流量调整值为容量与现有流量的差，即θi=cij-fij，而后向弧的流量调整值为现有流量，即θi=fij.
（2）求出整条增广链上流量的调整值，它应是所有弧的流量调整值的最小值，即θ=
，图9-38中增广链vs→v2→v5→v1→v4→vt流量的调整值为θ=
.（3）调整增广链的流量，具体做法是将增广链前向弧的现有流量加上流量调整值，将后向弧减去流量调整值，于是就得到了新流量的链，如图
9 39（a）所示，并得到新的网络图，如图
9-39（b）所示.
按上述方法找出网络图中所有增广链并依次调整每条增广链的流量，使其达到饱和状态.当再也找不到新的增广链时，此时源的流出量（或汇的流入量）就是网络图的最大流，如图9-39（b）所示.此时网络的最大流为11.
图9-39
例2 计算引例中从vs到vt的最大输油量，如图9-40所示.
图9-40
解 第一条增广链为vs→v3→v4→vt，流量调整值为
调整流量得图9-41.
第二条增广链为vs→v1→v2→vt，流量调整值为
调整流量得图9-42.
图9-41
图9-42
在图中再也找不到增广链，因此这时源的流出量（或汇的流入量）即为网络图的最大流，最大流为8，也就是说从源到汇，管道的最大输油能力为8.