Network Flow The Ford-Fulkerson Method: The previous theorem suggests a way to construct a maximum flow by iterative improvement a One keeps finding an augmenting path arbitrarily and increases the flow by its bottleneck capacity
The Ford-Fulkerson Method: ◼ The previous theorem suggests a way to construct a maximum flow by iterative improvement ◼ One keeps finding an augmenting path arbitrarily and increases the flow by its bottleneck capacity Network Flow
Network Fow Input:A network(G,s,t c); ■ Output:A flow in G; ■ 1.Initialize the residual graph:RG ■ 2.for each edge(u)∈E 3.u0k-0; 4.end for; 5.while there is an augmenting path p=s,...,tin R ■ 6. Let A be the bottleneck capacity of p; ■ 7. for each edge (u,v)in p ■ 8. u,)←-山☑+△； ■ 9. end for; ■ 10. Update the residual graph R; ■ 11.end while;
◼ Input: A network (G, s, t, c); ◼ Output: A flow in G; ◼ 1. Initialize the residual graph: RG; ◼ 2. for each edge (u, v)E ◼ 3. f(u, v)0; ◼ 4. end for; ◼ 5. while there is an augmenting path p=s, …, t in R ◼ 6. Let be the bottleneck capacity of p; ◼ 7. for each edge (u, v) in p ◼ 8. f(u, v) f(u, v)+ ; ◼ 9. end for; ◼ 10. Update the residual graph R; ◼ 11. end while; Network Flow