An Algorithm to Find Minimum Cost Flow in a Network.
Abstract
The paper describes an algorithm to find a flow of minimum cost in a network and a computer program which performs this algorithm. The principle of the algorithm is the following: At each iteration distances, which depend on the current flow, are defined on each arc and then a circuit of negative length is looked for. If such a circuit exists, more flow is pushed into it and a 'better' flow is found; if no such circuit exists, current flow is optimal. What might make this algorithm efficient is the fact that the information which has been gathered at some iteration to find a negative circuit will be used to find a negative circuit at next iteration so that each iteration requires a relatively small amount of work. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Nov 01, 1970
- Accession Number
- AD0715620
Entities
People
- A. Fillet
- M. Sakarovitch
- P. Giraud
Organizations
- University of California, Berkeley