Max Flow and Ford-Fulkerson Algorithm
Some real life problems like those involving the flow of liquids through pipes,current through wires and delivery of goods can be modeled using flow networks.
Network Flow
A network flow in directed graph G=(V,E) such that
For Each edge(u,v)=E associate a non-negative capacity c(u,v)>=0.If (u,v)∉ E assume that c(u,v)=0.
There are two distinguished points where source s and the sink t.
For every vertex v∈ V there is a path from s to t containing v.
- Capacity Constraint:- For all u,v∈ V require f(u,v)<=c(u,v).
- Skew Symmetry:-For all u,v∈ V require f(u,v)=-f(u,v).
Ford Fulkerson Algorithm
The Ford Fulkerson method is iterative.Start with f(u,v)=0 for all u,v ∈ V giving an initial flow of value 0.At each iteration increase the flow value by finding an "augmenting path" which can think of simply as a path from source s to the sink t along which can push more flow and then augmenting the flow along the path.Repeat this process until no augmenting path can be found.
An augmenting path p is a simple path from s to t in the residual network Gf. Residual network each edge (u,v) on an augmenting path admits some additional positive net flow from u to v without violating the capacity constraint on the edge.
The residual capacity is the maximal amount of flow that can be pushed through the augmenting path.
Max Flow Ford Fulkerson Algorithm
Step1 For each edge(u,v) ∈ E.
Step2 Do f[u,v] ← 0.
Step3 f[u,v] ← 0.
Step4 while there exists a path p from s to t in the residual network Gf.
Step5 Do Cf(p)←min{Cf(u,v):(u,v) is in p}.
Step6 For each edge (u,v) in p.
Step7 Do f(u,v)←f(u,v)+ Cf(p).
Step8 f[u,v]←-f[u,v].
Analysis of Ford-Fulkerson
The running time of Ford-Fullkerson depends on how the augmenting path p in line 4 is determined.If it is chosen poorly the algorithm might not even terminate.The value of the flow will increase with successive augmentations,but it need not even coverage to the maximum flow value.If the augmenting path is chosen by using a breadth first search the algorithm runs in polynomial time.
0 Comments