4.6. The labelling algorithm
The above algorithm works if we want get a maximal flow, but the efficiency of the algorithm is not too good. The first efficient algorithm for the max flow problem was investigated by L. R. Ford and D. L. Fulkerson in 1957. It was the labelling method. To understand this method we need to introduce some definitions.
Let be an arc in a
directed graph and,
be the capacity
of this edge and let
be the flow in
the arc. Then we call a
-
f-zero if ,
-
f-positive if
,
-
f-unsaturated if ,
-
f-saturated if .
We recall the definition of ε:
Let be a directed
graph and let f be a flow in
, and let a
be an arc in a path
. Then
then
From the above definition it is clear that is the largest
value by which the flow along P can be increased without violating the
condition
.
We will say that
the path P is f-saturated
if and f-unsaturated if
. An f-incrementing path is
an f-unsaturated path from the source s to the sink t.
The existence of an f-incrementing path P implies that f is not a maximum flow. Therefore, by sending an augmenting flow along P
one can obtain a new flow
defined by
Clearly, , and
the following theorem is true.
Theorem 4.15. A flow in a directed graph is a maximum flow iff the graph contains no f-incrementing path.
The following
example shows a graph with an actual flow. In this graph we consider an
incrementing path: .
The starting
flow value is . For the arcs the ε
values are:
,
,
,
.
Therefore . The right-hand side graph shows the revised flow
which based on the path P. Here the
flow value is
.

Figure 4.5. An incrementing-path and the revised flow.
So, we can construct an algorithm: let us start with a known flow, for instance the zero flow, and the algorithm recursively constructs a sequence of flows of increasing value, and terminates with a maximum flow.
How can we find an incrementing-path?
A tree T in a directed graph is an f-unsaturated tree if
-
-for
every vertex v of T, the unique path in T
is an f-unsaturated path.
The search for an f-incrementing
path involves growing an f-unsaturated tree in .
- Initially, T consists of just the source s.
- At any stage, there are two ways in which the tree may grow:
-
If there exists an f-satureted
arc a in , where
, then both a and its head are adjoined to T.
-
If there exists an f-positive
arc a in , then both a and its tail are adjoined to T.
It is clear, that the resulting T either reaches the sink t, or stops growing before reaching t.
- If the sink has been reached, then the -path in T is our desired f-incrementing
path.
- If T stops growing before reaching t, then f is a maximum flow.
As an unsaturated tree has been found, we need to choose an incrementing-path. To do that we will use the "first-labelled, first-scanned" procedure that was investigated by Edmonds and Karp (1972). The labelling procedure:
-
Assign to the source s
the label .
-
If a is an f-unsaturated
arc whose tail u is already labelled but whose head v is not,
then v is labelled .
-
If a is an f-positive
arc whose head u is already labelled but whose tail v is not,
then v is labelled .
In the above cases v is said to be labelled based on u.
To scan a labelled vertex u is to label all unlabelled vertices that can be labelled based on u.
The labelling procedure is continued until either the sink t is labelled (breakthrough) or all labelled vertices have been scanned and no more vertices can be labelled (implying that f is a maximum flow).
Figure 4.6. The algorithm "first-labelled, first-scanned"