Sunday, April 6, 2014

The basic Ford Fulkerson algorithm is given by the following:
Ford-Fulkerson(G, s, t)
for each edge (u,v) belonging to E[G]
   do f[u,v] = 0;
        f[v,u] = 0;
While there exists a path p from s to t in the residual network Gf
   do cf(p) = min[cf(u,v) : (u,v) is in p]
        for each edge (u,v) in p
             do f[u,v] = f[u,v] + cf(p)
                  f[v,u] = -f[u,v]


The Ford Fulkerson algorithm expands on the Ford Fulkerson method mentioned in the previous post. The while loop repeatedly finds an augmenting path p in Gf and augments flow f along the residual capacity cf (p). When no augmenting path exists, the flow f is the maximum flow.
How the augmentation is done determine s how well the algorithms performs.
If a breadth first traversal is chosen, the algorithm runs in polynomial time.
However let's first take the case when the augmentation path is chosen arbitrarily and the capacities are integral.
The complexity of the initialization steps are O (E)

The complexity of the while loop is O (E f*) where f* is the maximum flow through the system. The while loop is executed at most F* times. The efficiency of the while loop can be increased with the choice of a suitable data structure.



No comments:

Post a Comment