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

Circulation with Demands

Extend flow networks to handle node demands and supplies, modeling resource distribution problems.

Circulation with Demands

What you'll learn: How to model network flow problems where nodes themselves consume or produce resources, not just the source and sink.

The Core Idea

Until now, you've worked with flow networks where only the source supplies flow and only the sink consumes it. But real-world problems often involve intermediate nodes that need resources or produce extras. Think of a supply chain: warehouses need certain inventory amounts, factories produce goods, and distribution centers both receive and ship products.

Circulation with demands extends flow networks by assigning each node a demand value:

  • Positive demand (d(v) > 0): the node needs that much flow delivered
  • Negative demand (d(v) < 0): the node supplies that much flow (it's a source of resources)
  • Zero demand (d(v) = 0): the node is just a transit point

The goal is to find a valid circulation—a flow that satisfies:

  1. Capacity constraints on all edges (as usual)
  2. Flow conservation with demands: for every node v, the incoming flow minus outgoing flow must equal d(v)

Converting to Standard Max Flow

You can solve circulation problems using max flow algorithms! Add a super-source s* and super-sink t*:

  • Connect s* to every node with negative demand (suppliers) with capacity equal to the supply amount
  • Connect every node with positive demand to t* with capacity equal to the demand
  • Run max flow from s* to t*

If the max flow value equals the total demand (sum of all positive demands), a feasible circulation exists.

Example Analogy

Imagine power stations generating electricity (negative demand) and cities consuming it (positive demand), with transmission lines (edges) having capacity limits. Circulation with demands finds whether you can satisfy all cities without overloading any line.

Key Takeaway: Circulation with demands generalizes flow networks to model real resource distribution where intermediate nodes have supply/demand requirements, solvable by reducing to standard max flow problems.