Source code online books for professionals by professionals

Supply and demand. Imagine that you’re managing some form of planetary delivery service (or, if you prefer a less 
fanciful example, a shipping company). You’re trying to plan out the distribution of some merchandise—popplers, for 
example. Each planet (or seaport) has either a certain supply or demand (measured in popplers per month), and your 
routes between these planets have a certain capacity. How do we model this?
In fact, the solution to this problem gives us a very nifty tool. Instead of just solving this specific problem (which 
is just a thinly veiled description of the underlying flow problem anyway), let’s describe things a bit more generally. 
You have a network that’s similar to the ones we’ve seen so far, except we no longer have a source or a sink. Instead, 

---

ChApTeR 10 
■
 MATChINgs, CuTs, ANd Flows 
223
each node v has a supply b(v). This value can also be negative, representing a demand. To keep things simple, we can 
assume that the supplies and demands sum to zero. Instead of finding the maximum flow, we now want to know if we 
can satisfy the demands using the available supplies. We call this a feasible flow with respect to b.
Do we need a new algorithm for this? Luckily, no. Reduction comes to the rescue, once again. Given a network 
with supplies and demands, we can construct a plain-vanilla flow network, as follows. First, we add a source s and a 
sink t. Then, every node v with a supply gets an in-edge from s with its supply as the capacity, while every node with a 
demand gets an out-edge to t, with its demand as the capacity. We now solve the maximum flow problem on this new 
network. If the flow saturates all the edges to the sink (and those from the source, for that matter), we have found a 
feasible flow (which we can extract by ignoring s and t and their edges).