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.

The best book available for this problem is Network Flows : Theory, Algorithms, and Applications by Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin.


Implementations

  • Goldberg's Network Optimization Codes (C) (rating 10)
  • NEOS - Network Enabled Optimization System (FORTRAN) (rating 9)
  • RAPID - Robust and Accurate Polygon Interface detection (FORTRAN) (rating 8)
  • LEDA - A Library of Efficient Data Types and Algorithms (C++) (rating 5)
  • Discrete Optimization Methods (Pascal) (rating 4)
  • Moret and Shapiro's Algorithms P to NP (Pascal) (rating 4)
  • Nijenhuis and Wilf: Combinatorial Algorithms (FORTRAN) (rating 3)
  • GraphEd -- Graph Editor and Layout Program (C) (rating 3)
  • Combinatorica (Mathematica) (rating 3)

    Related Problems

  • Edge and Vertex Connectivity
  • Graph Partition
  • Linear Programming
  • Matching
  • Shortest Path


    Previous Problem Next Problem

    View the graph for this file

    Bulletin Board
    About ``The Algorithm Design Manual''.
    Send us Mail
    The Stony Brook Algorithm Repository -- go to front page

    This page last modified on Wed Mar 07, 2001 .