No other path! 5/5 5 6/6 4 5/7 1/2 6 4/4 5/5 2 3 4/5 Find all the path and increase its flow value to the max!
No other path! 6 4 5 2 3 1 1/2 5/5 4/5 4/4 5/7 5/5 6/6 Find all the path and increase its flow value to the max!
FORD-FULKERSON-METHOD(G.s.t) 1 initialize flow f to 0 2 while there exists an augmenting path p in the residual network Gf 3 augment flow f along p 4 return f 找到所有的augmenting path是方法的关键所在！
找到所有的augmenting path是方法的关键所在!
再看这个流网络中的流f: 5/5 5 5/6 4 5/7 2 当前流f下的 4/4 4/5 2 3 残存运力C 4/5 4 4 5 2 0 2 当前流下的残存网络G
再看这个流网络中的流f： 6 4 5 2 3 1 2 4/5 4/5 4/4 5/7 5/5 5/6 6 4 5 2 3 1 2 1 1 0 2 0 1 当前流f下的 残存运力Cf 6 4 5 2 3 1 2 1 1 1 2 当前流f下的残存网络Gf
借助残存运力/网络概念，再看上述寻找过程 Over? ▣
借助残存运力/网络概念，再看上述寻找过程 6 4 5 2 3 1 5 5 4 7 5 6 2 6 4 5 2 3 1 5 5 4 5 3 4 2 6 4 5 2 3 1 5 5 4 1 2 2 6 4 5 2 3 1 1 1 1 2 6 2 4 5 2 3 1 1 2 Over？ 1
A flow in a residual network provides a roadmap for adding flow to the original flow network.If f is a flow in G and f is a flow in the corresponding residual network Gf,we define f t f',the augmentation of flow f by f',to be a function from Vx V to R,defined by (f↑f,)= fu,)+f'(u,) if(u,v)∈E, 1 otherwise
6 4 5 2 3 1 5 5 4 7 5 6 2 6 4 5 2 3 1 5 5 4 5 3 4 2 6 4 5 2 3 1 5 5 41 2 2