Network Flows - Part 7

Throughout this series, we've built a powerful framework: flow networks, maximum flows, the Max-Flow Min-Cut Theorem, efficient algorithms, and minimum-cost flows. In this final part, we'll see how minimum-cost flows serve as a unifying tool — capturing classical optimization problems that, at first glance, seem to have nothing to do with networks. We'll then step back and reflect on how all the pieces fit together.

The Transportation Problem

One of the oldest problems in operations research is the transportation problem, formulated by Frank Hitchcock in 1941 and studied extensively by Tjalling Koopmans (who later won the Nobel Prize in Economics for this work). The setting is simple: several warehouses supply a product, several stores demand it, and shipping from each warehouse to each store has a known cost per unit. The goal is to meet all demand at minimum total shipping cost.

Formally, we have $p$ warehouses with supplies $s_1, \ldots, s_p$ and $q$ stores with demands $d_1, \ldots, d_q$, where the total supply equals the total demand: $\sum_i s_i = \sum_j d_j$. Shipping one unit from warehouse $i$ to store $j$ costs $w_{ij}$.

This is a minimum-cost flow problem in disguise. We construct the following network:

1. Create a source $s$ and a sink $t$.
2. For each warehouse $i$, add an arc $(s, i)$ with capacity $s_i$ and cost $0$.
3. For each warehouse $i$ and store $j$, add an arc $(i, j)$ with capacity $\min(s_i, d_j)$¹ and cost $w_{ij}$.
4. For each store $j$, add an arc $(j, t)$ with capacity $d_j$ and cost $0$.

A minimum-cost maximum flow in this network pushes exactly $\sum_i s_i = \sum_j d_j$ units from $s$ to $t$ (saturating all supply and meeting all demand) at minimum shipping cost. The flow on arc $(i,j)$ tells us how many units to ship from warehouse $i$ to store $j$.

Consider a small example. Two warehouses supply $s_1 = 5$ and $s_2 = 3$ units. Three stores demand $d_1 = 3$, $d_2 = 2$, and $d_3 = 3$ units. The shipping costs are:

The minimum-cost flow routes the goods along the cheapest paths: warehouse $1$ sends $3$ units to store $1$ (cost $6$) and $2$ units to store $3$ (cost $6$), warehouse $2$ sends $2$ units to store $2$ (cost $2$) and $1$ unit to store $3$ (cost $6$). Total cost: $20$. The successive shortest paths algorithm from Part 6 would find this solution automatically.

The Assignment Problem

A special case of the transportation problem arises when every supply and every demand is exactly $1$: we have $n$ agents and $n$ tasks, and each agent must be assigned to exactly one task. The cost of assigning agent $i$ to task $j$ is $w_{ij}$, and we want to minimize the total cost.

Definition 15. The assignment problem asks for a minimum-cost perfect matching between $n$ agents and $n$ tasks, given a cost matrix $w_{ij}$.

This is equivalent to finding a minimum-cost maximum flow in a bipartite network with unit capacities — combining the bipartite matching reduction from Part 5 with the cost dimension from Part 6.

The assignment problem has a rich history and a famous dedicated algorithm: the Hungarian method, developed by Harold Kuhn in 1955 (based on earlier work by Hungarian mathematicians Dénes König and Jenő Egerváry). The Hungarian method runs in $O(n^3)$ time, which is faster than applying a general min-cost flow algorithm. But conceptually, it can be understood as a specialized version of the successive shortest paths algorithm applied to a bipartite network with unit capacities².

Minimum-Weight Bipartite Matching

The assignment problem assumed equal numbers of agents and tasks and required a perfect matching. But we can also ask: given a bipartite graph with edge weights, find a maximum matching of minimum total weight. This is the minimum-weight bipartite matching problem.

The reduction to minimum-cost flow is almost identical to the assignment problem. We build a bipartite flow network with unit capacities (as in Part 5) and assign cost $w(a,b)$ to each arc from $A$ to $B$. Arcs from $s$ and to $t$ get cost $0$. A minimum-cost maximum flow then gives a maximum matching of minimum weight.

This generalizes our work on bipartite matchings from the graph theory series. In Part 8 of that series and Part 5 of this series, we found maximum matchings without caring about edge weights. Now, with minimum-cost flows, we can optimize over weighted matchings — a strictly more powerful tool.

Shortest Paths

Perhaps the most surprising reduction is that shortest paths — one of the most fundamental problems in graph theory — are a special case of minimum-cost flows.

Given a directed graph with arc costs $w(u,v)$ and two vertices $s$ and $t$, we want to find a shortest (cheapest) path from $s$ to $t$. This is a minimum-cost flow problem where every arc has capacity $1$ and we want to send exactly $1$ unit of flow from $s$ to $t$ at minimum cost.

Theorem 10. The shortest-path distance from $s$ to $t$ equals the minimum cost of sending one unit of flow from $s$ to $t$ in the network with unit capacities and costs equal to the arc weights.

Proof. A flow of value $1$ with integer values (guaranteed by the integrality theorem) must route exactly $1$ unit along a single $s$-$t$-path. The cost of the flow equals the total weight of that path. Minimizing the cost is therefore equivalent to finding the shortest path.

This might seem like overkill — why use the machinery of minimum-cost flows for shortest paths when Dijkstra's algorithm works perfectly well? The point is not practical but conceptual: it shows that minimum-cost flows sit at the top of a hierarchy of problems, with shortest paths as a special case.

The Network Flow Hierarchy

Let's step back and see how all the problems we've studied relate to each other. Each problem in the list below is a special case of the one above it:

Minimum-Cost Flow — the most general problem: find a flow that maximizes value and minimizes cost.

$\quad \uparrow$ (set all costs to zero)

Maximum Flow — find a flow of maximum value, ignoring costs.

$\quad \uparrow$ (unit capacities, bipartite structure)

Bipartite Matching — find a maximum set of disjoint edges in a bipartite graph.

$\quad \uparrow$ (add edge weights)

Minimum-Weight Bipartite Matching — find a maximum matching of minimum weight (uses min-cost flow).

Meanwhile, from a different angle:

Minimum-Cost Flow $\rightarrow$ (send exactly $1$ unit) $\rightarrow$ Shortest Paths

Maximum Flow $\rightarrow$ (unit capacities) $\rightarrow$ Edge-Disjoint Paths (Menger's theorem)

And the Max-Flow Min-Cut Theorem connects maximum flow to minimum cuts, while König's theorem connects bipartite matching to vertex covers. All of these dualities are instances of the same underlying principle: LP duality applied to network structures.

This hierarchy explains why network flow theory is so central to combinatorial optimization. By solving one general problem — minimum-cost flow — we can solve shortest paths, maximum matchings, transportation problems, assignment problems, and many more, all as special cases.

Wrapping Up the Series

We've come a long way since Part 1's supply chain motivation. Let's trace the journey:

Part 1 introduced network flows as a tool for real-world optimization. Part 2 laid the formal foundations with flow networks, flows, cuts, and weak duality. Part 3 proved the Max-Flow Min-Cut Theorem using residual graphs and augmenting paths. Part 4 turned theory into practice with the Ford-Fulkerson method and the Edmonds-Karp algorithm. Part 5 demonstrated the versatility of maximum flow through applications to bipartite matching, edge-disjoint paths, and project selection. Part 6 introduced costs, the negative cycle optimality condition, and algorithms for minimum-cost flows. And here in Part 7, we saw how minimum-cost flows unify a wide range of classical problems.

Throughout, we've seen a recurring theme: the interplay between primal objects (flows, matchings, paths) and dual objects (cuts, covers, bottlenecks). This duality — the idea that the best solution to one problem is always certified by the best solution to a related problem — is one of the deepest and most useful principles in all of optimization.

If you've followed both this series and the Introduction to Graph Theory, you now have a solid foundation in the combinatorial structures that underpin much of theoretical computer science and operations research. From Euler's bridges to minimum-cost flows, the journey has been one of increasing abstraction and power — and there is always more to explore.