Stony Brook Algorithm Repository


Network Flow

Input
Output

Input Description: A graph \(G\), where each edge \((i,j)\) has a capacity \(c_{i,j}\). A source node \(s\) and sink node \(t\).
Problem: What is the maximum flow you can route from \(s\) to \(t\) while respecting the capacity of each edge.

Excerpt from The Algorithm Design Manual: Applications of network flow go far beyond plumbing. Finding the most cost-effective way to ship goods between a set of factories and a set of stores defines a network flow problem, as do resource-allocation problems in communications networks and a variety of scheduling problems.

The real power of network flow is that a surprising variety of linear programming problems that arise in practice can be modeled as network flow problems, and that special-purpose network flow algorithms can solve such problems much faster than general-purpose linear programming methods. Several of the graph problems we have discussed in this book can be modeled as network flow, including bipartite matching, shortest path, and edge/vertex connectivity.


Implementations

GOBLIN (rating 10)
Goldberg's Network Optimization Codes (rating 10)
NEOS (rating 9)
LEDA (rating 8)
RAPID (rating 8)
PyMaxflow (rating 6)
Graph-Theory-Ford-Fulkerson-Maximum-Flow (rating 6)


Recommended Books

Network Coding Theory by R Yeung and S-Y. Li and N. Cai and Z. Zhang Network Flows : Theory, Algorithms, and Applications by Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin Introduction to Algorithms by T. Cormen and C. Leiserson and R. Rivest and C. Stein
Flows in Networks by L. Ford and D. R. Fulkerson

Related Problems


Edge and Vertex Connectivity

Graph Partition

Linear Programming

Matching

Shortest Path

Go To Main Page