Course contentsShow
← Computer Science
Lesson 1026 of 2,87224. Minimum Spanning Trees and Network FlowFree lesson

Maximum Flow Problem Statement

Formulate the maximum flow problem: finding the flow that maximizes the value from source to sink.

Maximum Flow Problem Statement

What you'll learn: How to formally define the problem of finding the largest possible flow from a source to a sink in a flow network.


Now that you understand flow networks, conservation, capacity constraints, and what makes a flow valid, we can state the optimization problem at the heart of network flow algorithms.

The Core Problem

Given a flow network with a source vertex s and a sink vertex t, the maximum flow problem asks: What is the maximum amount of flow we can push from s to t while respecting all capacity and conservation constraints?

Think of it like this: you have a water pipe network with a single water source and a single drain. Some pipes are narrow, some are wide (capacity limits). Water must flow continuously through junctions without accumulating (flow conservation). What's the maximum gallons per second you can deliver from source to drain?

Formal Statement

Find a valid flow f that maximizes the total flow value leaving the source (equivalently, entering the sink).

The flow value is the sum of all flow leaving s (or all flow entering t — they're equal by conservation). We want to maximize this single number while ensuring:

  • No edge carries more than its capacity
  • Every intermediate vertex conserves flow

Example Context

If your network represents a transportation system, the maximum flow tells you the maximum throughput. If it represents a communication network, it reveals bandwidth limits. If modeling supply chains, it identifies bottlenecks.

Key Takeaway: The maximum flow problem seeks the valid flow assignment that maximizes the total amount flowing from source to sink, subject to capacity and conservation constraints.