Advertisement
Guest User

Untitled

a guest
Feb 10th, 2016
72
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.55 KB | None | 0 0
  1. Algorithm Ford–Fulkerson
  2.  
  3. Inputs Given a Network $G = (V,E)$ with flow capacity $c$, a source node $s$, and a sink node $t$
  4. Output Compute a flow $f$ from $s$ to $t$ of maximum value
  5.  
  6. f(u,v) leftarrow 0 for all edges (u,v)
  7. While there is a path p from s to t in G_f, such that c_f(u,v) > 0 for all edges (u,v) in p:
  8. Find c_f(p) = min{c_f(u,v) : (u,v) in p}
  9. For each edge (u,v) in p
  10. f(u,v) leftarrow f(u,v) + c_f(p) (Send flow along the path)
  11. f(v,u) leftarrow f(v,u) - c_f(p) (The flow might be "returned" later)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement