next up previous
Next: References

Ford-Fulkerson Max Flow Labeling Algorithm

Harvey J. Greenberg
University of Colorado at Denver
http://carbon.cudenver.edu/ tex2html_wrap_inline332 hgreenbe/

December 22, 1998

The Ford-Fulkerson max flow labeling algorithm[3, 4] was introduced in the mid-1950's, and became the seminal work that is still applicable. The material presented in this note is taken from their book[5].

We are given a simple network with two specified nodes: source (s) and sink (t). Since the network is assumed to be simple, an arc is identified by its endpoints: (x,y) is the arc from node x to node y. A flow across arc (x,y) is denoted by f(x,y), and the arc's capacity is c(x,y). The flow must satisfy tex2html_wrap_inline350 .

The algorithm has two parts, which Ford and Fulkerson called Routine A and Routine B, respectively. The first is a labeling process that searches for a flow augmenting path - i.e., a path from s to t for which f < c along all forward arcs and f > 0 along all backward arcs. If Routine A finds a flow augmenting path, Routine B changes the flow accordingly. Otherwise, no augmenting path exists, and optimality of the current flow is ensured by their theorem:

Theorem.
A flow f has maximum value if, and only if, there is no flow augmenting path with respect to f.

We begin with any feasible flow (e.g., f=0). In general, a node is in one of three states: unlabeled, labeled and scanned, or labeled and unscanned. Upon entering Routine A, all nodes are unlabeled. The first step renders the source labeled and unscanned.

Routine A (labeling process). Initially, label the source tex2html_wrap_inline366 .

General step: Select any node, x, that is labeled and unscanned, and let tex2html_wrap_inline370 be its label. To all unlabeled successor nodes, y, such that f(x,y) < c(x,y), assign the label tex2html_wrap_inline376 , where

displaymath378

(Such y are now labeled and unscanned.) To all predecessor nodes, y, that are unlabeled, such that f(y,x) > 0, assign the label tex2html_wrap_inline386 , where

displaymath388

(Such y are now labeled and unscanned.) Now define x to be labeled and scanned. Repeat the general step until the sink is labeled and unscanned, or until no more labels can be assigned. In the former case, go to Routine B; in the latter case, terminate (f is a maximum flow).

Routine B (flow change). The sink has been labeled tex2html_wrap_inline396 . If the first part of the label is tex2html_wrap_inline398 , replace f(y,t) with tex2html_wrap_inline402 ; otherwise, replace f(t,y) with tex2html_wrap_inline406 . Go to node y and treat it the same way: if its label is tex2html_wrap_inline376 , replace f(x,y) with tex2html_wrap_inline414 ; if its label is tex2html_wrap_inline386 , replace f(y,x) with tex2html_wrap_inline420 . In either case, go to node x and repeat until the source is reached. Then, discard all labels and return to Routine A.

Example. The following is also taken from the Ford and Fulkerson book. The arc numbers are c(x,y),f(x,y). The initial flow sends one unit along the path (s,x,y,t).

tex2html_wrap466

The first execution of Routine A results in ``breakthrough'' (i.e., finding a flow augmenting path) with the following labels:

After one step in Routine A:

tex2html_wrap468

After two steps in Routine A:

tex2html_wrap470

After three steps in Routine A:

tex2html_wrap472

Breakthrough.

We now execute Routine B to obtain new flows:

tex2html_wrap474

After repeating Routine A, we finish with the following labels.

tex2html_wrap476

This shows that the flow can be increased by 1 (= tex2html_wrap_inline428 ) along the flow augmenting path, (s,(y,x),t). Working backwards from the sink, the path traverses arc (x,t) in a forward direction, so its flow increases by 1 (f(x,t) becomes 2). The label at x tells us we traverse arc (x,y) in a backward direction, so we decrease that flow by 1 ((f(x,y) becomes 0). We then move to node y, and its label tells us that the flow augmenting path traverses arc (s,y) in the forward direction, so its flow increases by 1 (f(s,y) becomes 2). Since we reach the source (s), Routine B terminates, and we return to Routine A with the following flows and initial label:

tex2html_wrap478

After executing Routine A, we find there is no flow augmenting path, so the current flow has the maximum value of 3 units from s to t. The final labels are shown:

tex2html_wrap480

Convergence

When the capacities are integer-valued, the flow increases by at least one unit each iteration, so termination must be finite. Further, in this case, it can be shown that it takes at most |V||E| iterations to terminate with a maximum flow. Chvátal[2] describes a pathology when the data are irrational. Let tex2html_wrap_inline466 (note the critical property: tex2html_wrap_inline460 for all tex2html_wrap_inline462 ) The following network [1] has arc capacities equal to tex2html_wrap_inline472 , except three arcs:

displaymath474

tex2html_wrap482

The Ford-Fulkerson max flow labeling algorithm yields a sequence of flow increases, but it does not terminate finitely. Here are the iterations that show a pattern of flow augmenting paths that continue cyclically.

displaymath476




next up previous
Next: References

Harvey Greenberg
Wed Dec 23 09:00:14 MST 1998