Harvey J. Greenberg
University of Colorado at Denver
http://carbon.cudenver.edu/ 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 .
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:
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.
General step: Select any node, x, that is labeled and
unscanned, and let be its label. To all
unlabeled successor nodes, y, such that f(x,y)
< c(x,y), assign the label
, where
(Such y are now labeled and unscanned.) To all predecessor nodes,
y, that are unlabeled, such that f(y,x) > 0,
assign the label , where
(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).
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).
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:
After two steps in Routine A:
After three steps in Routine A:
Breakthrough.
We now execute Routine B to obtain new flows:
After repeating Routine A, we finish with the following labels.
This shows that the flow can be increased by 1 (= ) 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:
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:
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 (note the critical property:
for all
) The following
network [1]
has arc capacities equal to
, except three arcs:
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.
Harvey Greenberg