liveBook · Manning

Maximum flow

The maximum flow problem is finding the greatest feasible flow from a source to a sink in a capacitated network while respecting capacity and flow-conservation constraints.

How 3 Manning books explain it

Algorithms Every Programmer Should Know

The problem of finding the greatest feasible flow from a source to a sink in a capacitated network.

How it is used
Measures the greatest feasible source-to-sink throughput in a capacitated network.
How deep it goes
Works through preflow, excess, push, relabel, and a four-node trace, then gives implementation and complexity details.
Examples
Traces a four-node network carrying 15 units and models baseball elimination using remaining games and allowable wins.
What you can do after
Build it from scratch with a Python Push–Relabel implementation that computes source-to-sink maximum flow.

Read how Algorithms Every Programmer Should Know explains maximum flow →

The Coder Cafe

The maximum flow problem asks for the greatest feasible flow from a source to a sink without exceeding edge capacities.

How it is used
Frames maximum flow as finding the greatest source-to-sink throughput under edge-capacity limits.
How deep it goes
Explains terminology and iterative flow updates with pseudocode, but leaves path-finding and bottleneck helpers unspecified.
Examples
Illustrates open and blocked paths, plus pipeline, data-network, and traffic-flow scenarios.
What you can do after
Evaluate/understand it by tracing augmenting-path updates and recognizing when no further path is available.

Read how The Coder Cafe explains maximum flow →

Advanced Algorithms and Data Structures

Maximum flow is the problem of sending the greatest possible amount through a capacitated network from a source to a sink while respecting edge capacities and flow conservation.

How it is used
Models routing through capacitated directed networks as an optimization problem.
How deep it goes
Defines networks, capacities, conservation, and routing choices, then stops short of a complete solving algorithm.
Examples
Uses hydraulic pipes, a D-F-G routing scenario, and chromosome assignments illustrated on a network.
What you can do after
Evaluate/understand whether candidate edge assignments satisfy flow constraints and maximize delivery to the sink.

Read how Advanced Algorithms and Data Structures explains maximum flow →

What to know first

Related concepts

Questions about maximum flow

What is maximum flow?

The maximum flow problem is finding the greatest feasible flow from a source to a sink in a capacitated network while respecting capacity and flow-conservation constraints.

Which Manning books explain maximum flow?

Algorithms Every Programmer Should Know, The Coder Cafe and Advanced Algorithms and Data Structures.

What should I know before learning maximum flow?

Manning books that teach maximum flow usually introduce breadth-first search first.

What is maximum flow a kind of?

Maximum flow is a kind of optimization. Optimization is the systematic selection or modification of values, configurations, or implementations to improve a defined objective, often subject to constraints.

These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.