(2)73)continue bWe claim that f(u,v=c(u,v) for all u∈ S and v∈T, The Basic Ford-Fulkerson if not, it implies that(u, v)EE which implies that v should be in s【矛盾!】, therefore, >f=f(S,TFc(,T) s Ford-Fulkerson(G, s, t) 1. For each edge (u,v)in E[G P(3)(1): by corollary 26.6, fsc(s, T) for all cuts 1.uyvl←0 (S,T), then the condition f=c(s, T)thus implies 2. fv, u]e0 that f is a maximum flow While there exists a path p from s to t in the residual 1.cp)∈ mined, v):(u, v)in p} 2. For each edge(u, v)in p lu,v]e fu,vl+ cdp 清华大学就件学院末恒 请华大学轼件学院宋斌恒 Analysis of Ford-Fulkerson The estimation of x s Initializing: O(E) Case 1. If all of the capacity values are integer Ev then xsf where f* is the maximum flow of X Find a path p on G: O(E+VO(E)if using BFS or des Proof: At every augmenting step the flow increases at least 1. hence x does not exceed f 2* compute cdp): O(V) a It can expand the case rational numbered 2* Augmenting f: OV) ?How many steps of augmenting? If it is x rk: computer can only treat rational hen the total running time is O(vx) 清华大学软件学院宋恒 請华大学轼件学院宋斌包 7 s Explanation of Ford-Fulkerson's Algorithm 找路径 4/ 4/4改变流 南华大学软件学院宋就恒 414院 66 清华大学 软件学院 宋斌恒 31 (2)Î(3) [continue] We claim that f(u,v)=c(u,v) for all u∈S and v∈T, if not, it implies that (u,v) ∈Ef , which implies that v should be in S【矛盾！】, therefore, |f|=f(S,T)=c(S,T) (3)Î(1): by corollary 26.6, |f|≤c(S,T) for all cuts (S,T), then the condition |f|=c(S,T) thus implies that f is a maximum flow. 清华大学 软件学院 宋斌恒 32 The Basic Ford-Fulkerson algorithm Ford-Fulkerson(G,s,t) 1. For each edge (u,v) in E[G] 1. f[u,v]Å0 2. f[v,u]Å0 2. While there exists a path p from s to t in the residual network Gf 1. cf (p)Åmin{cf (u,v): (u,v) in p} 2. For each edge (u,v) in p 1. f[u,v]Å f[u,v]+ cf (p) 2. f[v,u]Å - f[u,v] 清华大学 软件学院 宋斌恒 33 Analysis of Ford-Fulkerson Initializing: O(E) Every augmenting: Find a path p on Gf : O(E+V)=O(E) if using BFS or DFS compute cf (p): O(V) Augmenting f: O(V) ?How many steps of augmenting? If it is x then the total running time is O(Vx) 清华大学 软件学院 宋斌恒 34 The estimation of x Case 1. If all of the capacity values are integer, then x≤f*, where f* is the maximum flow of the flow network. Proof: At every augmenting step the flow increases at least 1, hence x does not exceed f*. It can expand the case rational numbered capacity. Remark: computer can only treat rational number! 清华大学 软件学院 宋斌恒 35 Explanation of Ford-Fulkerson’s Algorithm 清华大学 软件学院 宋斌恒 36 1 3 2 4 s t 1 3 2 4 s t 找路径 改变流