Graph Theory37 sections · 1633 units
Open in Course

Multiple Sources and Sinks

Reduction to single source/...

Some problems have multiple sources or sinks. Convert them to single-source single-sink by adding a super-source and super-sink. Super-source connects to all original sources with infinite capacity.

Super-sink connects from all original sinks with infinite capacity. Run max flow on the modified graph. The result is the same as if you had multiple sources and sinks. This technique is standard. The added edges do not change the flow structure. They simply aggregate supply and demand.