Maximum Flow

From Progteam

Revision as of 05:14, 7 February 2009 by Jinho (Talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Maximum Flow:

**images coming soon**

Consider a directed graph G (V, E) in which V represents the collection of vertices and E the collection of edges. The edges have a capacity Cv,w . We name two of the vertices S and T, the source and the sink, such that all flow through the graph originates at the source and ends at the sink. The problem consists of finding the maximum flow that can leave the source and enter the sink without violating edge capacities.

A simple solution is as follows: Starting with the graph G, create a flow graph F, identical to G but with the flow of each vertex set to zero. This graph will contain the flow attained at any point in the algorithm. Create a third graph, the residual graph R, initially identical to G. R will contain the flow which has yet to be assigned to the flow graph, in other words the potential flow that remains in G at any point in the algorithm. The algorithm will continue to run as long as there exists a path in R from S to T. At each stage we will find such a path (This can be done by preforming a search for T starting at S). If the minimum capacity of this path is greater than 0, add this path (containing its maximum capacity) to F. We remove that path from R, then add an edge of equal value but opposite direction. This step is necessary in order to find the maximum flow in every case.

Input: A directed graph G(V,E) with capacities  Cv,w 
Output: A flow graph F containing the maximum flow

R = the residual graph, with all capacities equal to that of G
F = the flow graph, with all capacities set to 0

while there exists a path in R from s to t with a C > 0
  U = a collection of edges forming a path from s to t with capacity >0 
  min = the capacity of the edge in U with the smallest capacity
  for each edge (v, w) in F add min to Cv,w
  for each edge (v, w) in R subtract min from Cv,w and add min to (w, v) in R
Personal tools