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

Maximum Flow Problem Definition

Understand flow networks, source/sink nodes, capacities, and the goal of maximizing flow from source to sink.

Maximum Flow Problem Definition

What you'll learn: You'll understand what the maximum flow problem asks us to solve in a flow network.


Now that you've learned about flow networks, residual networks, augmenting paths, and the max-flow min-cut theorem, let's formally define the problem we're trying to solve.

The Core Problem

Given a flow network with:

  • A source node (where flow originates)
  • A sink node (where flow terminates)
  • Edges with capacities (maximum flow each edge can carry)
  • Flow conservation at all intermediate nodes (flow in = flow out)

The maximum flow problem asks: What is the largest amount of flow we can push from the source to the sink while respecting all capacity constraints?

Understanding the Goal

Think of water pipes connecting a water tower (source) to a city (sink). Each pipe has a maximum capacity. Some pipes connect to intermediate junctions. The question is: How much water can we deliver to the city?

We want to find a valid flow (satisfying capacity and conservation constraints) where the total flow leaving the source—which equals the total flow entering the sink—is as large as possible.

What Makes It a Problem?

The challenge is that paths from source to sink share edges. Sending more flow along one path might "use up" capacity that could have been better utilized by a different combination of paths. The maximum flow problem requires finding the optimal way to distribute flow across all possible paths.


Key Takeaway: The maximum flow problem asks us to find the largest total flow we can send from a source node to a sink node in a flow network while respecting all edge capacities and flow conservation constraints.