Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- Algorithm Ford–Fulkerson
- Inputs Given a Network $G = (V,E)$ with flow capacity $c$, a source node $s$, and a sink node $t$
- Output Compute a flow $f$ from $s$ to $t$ of maximum value
- f(u,v) leftarrow 0 for all edges (u,v)
- 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:
- Find c_f(p) = min{c_f(u,v) : (u,v) in p}
- For each edge (u,v) in p
- f(u,v) leftarrow f(u,v) + c_f(p) (Send flow along the path)
- 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