# NETWORK FLOW THEORY

Original Publication Date: 1956-Aug-14

Included in the Prior Art Database: 2005-Sep-19

## Publishing Venue

Software Patent Institute

## Related People

Ford, Jr., L.R.: AUTHOR [+2]

## Abstract

A network (or linear graph) is a collection of points or nodes, some of which may be joined together by arcs. We shall denote the points by P i , i = 0, 1, 2, ..., N. and denote the arc joining P i to P j in that order by A ij . (Note that there may also be an arc A ji joining P j to P i .) We may also have associated with the arc A ij a capacity c ij and a length (or cost) l ij . We shall assume these to be positive integers. We shall also distinguish two points in the network, P O , the origin, and P N , the terminal. One may think of this system as a rail network, in which the origin represents a factory or a warehouse at which goods enter the system, and the terminal represents a consumer for these goods who removes them from the system. The c ij then represent upper bounds on the shipping capacity from P i to P j and the l ij may represent variously the distance from P i to P j or the time required to ship from P i to P j or the unit cost of shipping from P i to P j . (We shall agree that if c ij = 0 then l ij = &infty; and that l ij &neq; 0.) Evidently many different problems may be posed with this framework. We shall discuss primarily the following three problems, stated verbally below. A. To find a maximal steady state flow of goods from the origin to the terminal, independent of cost consideration (i.e. of l ij ). B. To find the cheapest route from origin to terminal independent of capacity constraints (i.e. of c ij ). C. To find the maximal amount of goods that can be shipped from origin to terminal in a given time, T (here interpreting l ij as the time required to ship from P i to P j ). We shall discuss A first as being by far the richest in applications. It appears as a subproblem in a very large number of transportation-type problems, and from the theory which we shall develop one may obtain a large number of combinatorial results as well.

**This text was extracted from a PDF file.**

**This is the abbreviated version, containing approximately 22% of the total text.**

__Page 1 of 7__THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

**NETWORK FLOW THEORY **

L. R. Ford, Jr.

P-923
August 14, 1956

The RAND Corporation
1700 MAIN ST. SANTA MONICA CALIFORNIA

**SUMMARY **

The labeling algorithm for the solution of maximal network flow problems and its application to various problems of the transportation type are discussed.

**NETWORK FLOW THEORY [ title ] **

L. R. Ford, Jr.

**1. INTRODUCTION **

A network (or linear graph) is a collection of points or nodes, some of which may be joined
together by arcs. We shall denote the points by P_{i}, i = 0, 1, 2, ..., N. and denote the arc joining P_{i}
to P_{j} in that order by A_{ij}. (Note that there may also be an arc A_{ji} joining P_{j} to P_{i}.) We may also
have associated with the arc A_{ij} a capacity c_{ij} and a length (or cost) l_{ij}. We shall assume these to
be positive integers. We shall also distinguish two points in the network, P_{O}, the origin, and P_{N},
the terminal. One may think of this system as a rail network, in which the origin represents a
factory or a warehouse at which goods enter the system, and the terminal represents a
consumer for these goods who removes them from the system. The c_{ij} then represent upper
bounds on the shipping capacity from P_{i} to P_{j}and the l_{ij} may represent variously the distance
from P_{i} to P_{j} or the time required to ship from P_{i} to P_{j} or the unit cost of shipping from P_{i} to P_{j}.
(We shall agree that if c_{ij} = 0 then l_{ij} = ∞ and that l_{ij} ≠ 0.)

Evidently many different problems may be posed with this framework. We shall discuss primarily
the following three problems, stated verbally below.

A. To find a maximal steady state flow of goods from the origin to the terminal, independent of
cost consideration (i.e. of l_{ij}). B. To find the cheapest route from origin to terminal independent of
capacity constraints (i.e. of c_{ij}).

C. To find the maximal amount of goods that can be shipped from origin to terminal in a given
time, T (here interpreting l_{ij} as the time required to ship from P_{i} to P_{j}).

Rand Corporation Page 1 Aug 14, 1956

__Page 2 of 7__NETWORK FLOW THEORY

We shall discuss A first as being by far the richest in applications. It appears as a subproblem in a very large number of transportation-type problems, and from the theory which we shall develop one may obtain a large number of combinatorial results as well.

**2. FORMAL STATEMENT OF PROBLEM A **

A steady state flow of goods from origin to terminal is required to have the following properties:

(a) the amount flowing into P_{i} must equal the amount flowing out of P_{i} for i ≠ 0, N;

(b) the amount flowing along A_{ij }must be less than or equal to C_{ij}.

Subject to these restrictions, it is desired to maximize x_{F}, the amount flowing out of P_{0}, or
equivalently, the amount flowing into P_{N}. This may be presented as a linear programming
problem as follows. Denote by x_{ij} ≥ 0 the flow from P_{i} to P_{j}. Then [ Equation omitted ]

Thus Problem A could be solved by a direct application of the simplex method to the above system.

**3. SOLUTION O...**