33. Network Flow
q
Weighted directed graphs are useful models for several types of applica-
tions involving commodities flowing through an interconnected network.
Consider, for example, a network of oil pipes of varying sizes, interconnected
in complex ways, with switches controlling the direction of flow at junctions.
Suppose further that the network has a single source (say, an oil field) and a
single destination (say, a large refinery) to which all of the pipes ultimately
connect. What switch settings will maximize the amount of oil flowing from
source to destination? Complex interactions involving material flow at junc-
tions make this problem, called the problem, a nontrivial problem
to solve.
This same general setup can be used to describe traffic flowing along
highways, materials flowing through factories, etc. Many different versions
of the problem have been studied, corresponding to many different practical
situations where it has been applied. There is clearly strong motivation to
find an efficient algorithm for these problems.
This type of problem lies at the interface between computer science
and the field of operations research. Operations researchers are generally
concerned with mathematical modeling of complex systems for the purpose
of (preferably optimal) decision-making. Network flow is a typical example
of an operations research problem; we’ll briefly touch upon some others in
Chapters 37-40.
As we’ll see, the modeling can lead to complex mathematical equations
that require computers for solution. For example, the classical solution to the
network flow problem given below is closely related to the graph algorithms
that we have been examining. But this problem is one which is still actively
being studied: unlike many of the problems that we’ve looked at, the “best”
solution has not yet been found and good new algorithms are still being
discovered.
433

capacities. Now, a flow is defined as another set of weights on the edges such
that the on each edge is equal to or less than the capacity, and the flow
into each vertex is equal to the flow out of that vertex. The value of the flow
is the flow into the source (or out of the sink). The network problem is
to find a flow with maximum value for a given network.
Networks can obviously be represented using either the adjacency matrix
or adjacency list representations that we have used for graphs in previous
chapters. Instead of a single weight, two weights are associated with each
edge, the size and the Aow. These could be represented as two fields in an
adjacency list node, as two matrices in the adjacency matrix representation,
or as two fields within a single record in either representation. Even though
networks are directed graphs, the algorithms that we’ll be examining need
to traverse edges in the “wrong” direction, so we use an undirected graph
representation: if there is an edge from x to y with size s and flow we also
keep an edge from y to x with size and flow -f. In an adjacency list
representation, it is necessary to maintain links connecting the two list nodes
which represent each edge, so that when we change the flow in one we can
update it in the other.
Ford-Fulkerson Method
The classical approach to the network flow problem was developed by L. R.
Ford and D. R. Fulkerson in 1962. They gave a method to improve any legal
flow (except, of course, the maximum). Starting with a zero flow, we apply
the method repeatedly; as long as the method can be applied, it produces an
increased if it can’t be applied, the maximum flow has been found.
Consider any directed path through the network (from source to sink).
Clearly, the flow can be increased by at least the smallest amount of unused
capacity on any edge on the path, by increasing the flow in all edges on the
436
33
path by that amount. In our example, this rule could be applied along the

network, provided that a path with no full forward edges or empty backward
edges can be found. The crux of the Ford-Fulkerson method is the observation
that if no such path can be found then the flow is maximal. The proof of
this fact goes as follows: if every path from the source to the sink has a full
forward edge or an empty backward edge, then go through the graph and
identify the first such edge on every path. This set of edges cuts the graph in
two parts, as shown in the diagram below for our example.