Ford-Fulkerson算法框架 ·基本思路 查找f可增路P -反复查找是否存在f可增路P ·如果存在，沿P则更新当前流f P=null? ·否则f即为最大流 N FORD-FULKERSON(G.S.t) for each edge (u.v)EG.E 更新当前流f 2 (4,v)f=0 while there exists a path p from s to t in the residual network Gf 4 cf(p)=mincf(u.v):(u.v)is in p 5 for each edge (u.v)in p 返回当前流f if(u,v)∈E 7 (u.v).f=(u.v).f+cf(p) 8 else (v.u).f =(v.u).f-cf(p)Ford-Fulkerson算法框架 • 基本思路 – 反复查找是否存在𝒇可增路P • 如果存在,沿P则更新当前流𝒇 • 否则𝒇即为最大流 查找𝒇可增路P P=null? 更新当前流𝒇 返回当前流𝒇 N Y