The Algorithm Design Manual
About the Book
Programming Challenges

The Stony Brook Algorithm Repository

Steven Skiena
Stony Brook University
Dept. of Computer Science

1.4.9 Network Flow

Problem Input | Problem Output

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

  • Goldberg's Network Optimization Codes (C) (rating 10)
  • GOBLIN: A Graph Object Library for Network (C++) (rating 9)
  • NEOS - Network Enabled Optimization System (FORTRAN) (rating 9)
  • LEDA - A Library of Efficient Data Types and Algorithms (C++) (rating 8)
  • RAPID - Robust and Accurate Polygon Interface detection (C,FORTRAN) (rating 8)
  • Kenji Ikeda's Ford-Fulkerson's Algorithm page (Java) (rating 5)

  • 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



    This page last modified on 2008-07-10 .
    www.algorist.com