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.

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) |

Edge and Vertex Connectivity |
Graph Partition |
Linear Programming |

Matching |
Shortest Path |

As an Amazon affiliate, I earn from qualifying purchases if you buy from links on this website.