Network Optimization Models
A map of cities and roads, a power grid, a pipeline, a project schedule — draw them all as a graph of nodes joined by arcs and a surprising number of optimization problems fall into a single family. This chapter studies four classics on such networks: the shortest path between two nodes, the cheapest tree that connects every node, the largest flow a network can carry, and the least-cost way to route supplies to demands. Each has an elegant, purpose-built algorithm, and all four turn out to be special cases of one grand model — the minimum-cost flow problem.
- The language of networks — nodes, arcs, paths, cycles, trees, and flows.
- The shortest-path problem and Dijkstra's algorithm for nonnegative arc lengths.
- The minimum spanning tree and why the greedy (Prim/Kruskal) rule is exactly optimal.
- The maximum-flow problem and the Ford–Fulkerson augmenting-path method.
- The max-flow min-cut theorem — the bottleneck that limits every network.
- The minimum-cost flow model that unifies transportation, assignment, shortest path, and max flow.
Networks and Terminology
A network (or graph) \(G = (N, A)\) is a set of nodes \(N\) joined by a set of arcs \(A\). An arc \((i, j)\) connects node \(i\) to node \(j\); it is directed if flow may travel only from \(i\) to \(j\), and undirected if it may go either way. A path is a sequence of arcs leading from one node to another; a cycle is a path that returns to its start. A network is connected if a path joins every pair of nodes, and a tree is a connected network with no cycles — a tree on \(n\) nodes has exactly \(n-1\) arcs. A spanning tree is a tree that reaches every node of the network.
When arcs carry weights, those numbers can mean different things — a length or cost, a capacity limiting flow, or a per-unit shipping cost — and each interpretation gives a different optimization problem. The rest of this chapter works through the four most important, using the network above (and one directed network) as running examples.
The Shortest-Path Problem
Given a network with a nonnegative length on each arc, the shortest-path problem asks for the path of least total length from a source node to a destination (or from the source to every other node). Dijkstra's algorithm solves it by growing a set of permanently labelled nodes whose shortest distance from the source is already known.
Keep a tentative distance \(d(i)\) for every node, initialised to \(0\) at the source and \(\infty\) elsewhere. Repeat: select the unlabelled node \(i\) with the smallest \(d(i)\) and mark it permanent; then relax each arc \((i,j)\) out of it, setting \(d(j) \leftarrow \min\{\,d(j),\ d(i) + \ell_{ij}\,\}\). Because arc lengths are nonnegative, the smallest tentative label can never later be improved — so labelling it permanently is safe.
Running Dijkstra from node 1: label 1 at \(0\); relax to get \(d(2)=2,\ d(3)=4\). The smallest is node 2 — make it permanent, and relaxing \((2,3)\) improves \(d(3)\) to \(2+1=3\). Node 3 is next at \(3\); relaxing \((3,5)\) gives \(d(5)=3+3=6\). Node 5 becomes permanent at \(6\), the shortest distance, along the path \(1 \to 2 \to 3 \to 5\).
Any other route to that node must pass through a still-unlabelled node whose distance is at least as large, and adding nonnegative arcs can only increase it. Nonnegativity is essential — with negative arcs Dijkstra can fail, and a label-correcting method (e.g. Bellman–Ford) is used instead.
The Minimum Spanning Tree Problem
The minimum spanning tree (MST) problem asks for the set of arcs of least total length that keeps every node connected. The answer is a spanning tree — \(n-1\) arcs, no cycles — and unlike the shortest-path problem it is about connecting all nodes cheaply, not travelling between two of them (think of laying cable or pipe to reach every building at minimum total length).
A simple greedy rule solves it exactly. In Kruskal's version, sort the arcs by length and add them cheapest-first, skipping any arc that would close a cycle, until \(n-1\) arcs are in. In Prim's version, grow one tree from an arbitrary node, each step adding the cheapest arc that joins a tree node to a node not yet in the tree.
On our network, sorting the arcs gives \(2\text–3(1),\ 4\text–5(1),\ 1\text–2(2),\ 3\text–5(3),\ 1\text–3(4),\ 3\text–4(5),\ 2\text–4(7)\). Adding them in order, the arc \(1\text–3\) is rejected because it would close the cycle \(1\text–2\text–3\); after four accepted arcs every node is connected, giving total length \(7\).
The Maximum-Flow Problem
Now put a capacity \(u_{ij}\) on each directed arc — the most flow it can carry. The maximum-flow problem asks how much can be sent from a source \(s\) to a sink \(t\) at once, with flow on every arc kept within its capacity and conserved at every intermediate node (what flows in flows out).
The Ford–Fulkerson method builds the answer one augmenting path at a time. Find any path from \(s\) to \(t\) whose arcs all have spare capacity (the residual), push flow equal to the smallest spare capacity along it (the bottleneck), and reduce each arc's residual accordingly — while adding residual capacity in the reverse direction, so flow can be rerouted later. Repeat until no augmenting path remains.
On the network above: send \(1\) along \(s\to a\to t\) (bottleneck \(1\)), then \(3\) along \(s\to a\to b\to t\) (bottleneck \(3\)), then \(1\) along \(s\to b\to t\) (bottleneck \(1\)). Now both arcs into \(t\) are full, so no augmenting path is left and the maximum flow is \(1+3+1 = 5\).
The Max-Flow Min-Cut Theorem
An \(s\)–\(t\) cut splits the nodes into two sets, one containing \(s\) and the other \(t\). Its capacity is the total capacity of the arcs pointing from the \(s\)-side to the \(t\)-side. Since every unit of flow must cross any such cut, no flow can exceed the smallest cut's capacity. The remarkable fact is that this bound is always achieved.
When Ford–Fulkerson stops, the nodes still reachable from \(s\) in the residual network form the \(s\)-side of a cut whose every forward arc is saturated — so its capacity equals the flow found, proving both values optimal at once. Here the cut isolating \(t\) has capacity \(1+4 = 5\), matching the maximum flow. The cut is the network's true bottleneck: relieve it and nothing else, and the throughput rises.
The Minimum-Cost Flow Problem
The minimum-cost flow problem is the most general model of the four. Each node \(i\) has a net supply \(b_i\) (positive at a source, negative at a demand, zero at a transshipment node), each arc has a per-unit cost \(c_{ij}\) and a capacity \(u_{ij}\). The task is to route the supplies to the demands at least total cost while respecting capacities and conserving flow at every node.
The equality constraints are the flow-conservation (node) equations: at each node, outflow minus inflow equals its net supply. For the model to be feasible, total supply must equal total demand, \(\sum_i b_i = 0\).
The node–arc incidence matrix is totally unimodular, exactly as in the transportation and assignment problems of the previous chapters. So the linear-programming relaxation automatically yields whole-number flows — no branch-and-bound required — and a specialised, very fast simplex variant, the network simplex method, exploits the tree structure of basic solutions to solve it far quicker than ordinary simplex.
A Unifying Framework
The power of the minimum-cost flow model is that the other network problems — and the transportation and assignment problems of Chapters 12 and 13 — are all special cases obtained by choosing the supplies, costs, and capacities appropriately:
| Special case | How to obtain it from min-cost flow |
|---|---|
| Transportation problem | Sources with supply \(b_i>0\), destinations with demand \(b_j<0\), arc costs \(c_{ij}\), no intermediate nodes |
| Assignment problem | A transportation problem with every supply and demand equal to \(1\) |
| Shortest-path problem | Send one unit from source \((b_s=1)\) to sink \((b_t=-1)\); arc costs are the lengths |
| Maximum-flow problem | Zero arc costs, a return arc \(t\to s\) of cost \(-1\); maximising its flow maximises throughput |
Worked Examples
Problem. A tree connects \(n = 6\) nodes. How many arcs does it have, and what happens if you add one more arc?
Solution. A tree on \(n\) nodes has exactly \(n-1 = 5\) arcs and no cycles. Adding any further arc joins two already-connected nodes, creating exactly one cycle — so the result is no longer a tree.
Problem. Using the five-node network, find the shortest distance from node 1 to node 5.
Solution. Permanent labels appear in the order \(d(1)=0,\ d(2)=2,\ d(3)=3,\ d(5)=6\). Relaxing \((2,3)\) improves node 3 from \(4\) to \(3\); relaxing \((3,5)\) then gives \(6\). The shortest path is \(1\to 2\to 3\to 5\) of length \(2+1+3 = 6\).
Problem. Find the minimum spanning tree of the same network by Kruskal's method.
Solution. Sort arcs: \(2\text–3(1),\,4\text–5(1),\,1\text–2(2),\,3\text–5(3),\,1\text–3(4),\dots\) Add \(2\text–3,\ 4\text–5,\ 1\text–2\), then \(3\text–5\) which links the two pieces; \(1\text–3\) is skipped (it would form a cycle). Four arcs connect all five nodes for a total length of \(1+1+2+3 = 7\).
Problem. In the directed capacity network, after sending \(1\) unit on \(s\to a\to t\), find the next augmenting path and its bottleneck.
Solution. The path \(s\to a\to b\to t\) still has residuals \(3,\ 3,\ 4\), so its bottleneck is \(3\); push \(3\) units. A final unit on \(s\to b\to t\) saturates both arcs into \(t\), leaving no augmenting path and a maximum flow of \(5\).
Problem. Verify the maximum flow of \(5\) using the max-flow min-cut theorem.
Solution. Take the cut with only \(t\) on one side. Its forward arcs are \(a\to t\) (capacity \(1\)) and \(b\to t\) (capacity \(4\)), so its capacity is \(5\). No cut is smaller, and a flow of \(5\) exists, so both are optimal — the two arcs into \(t\) are the bottleneck.
Problem. Show that a shortest-path problem is a minimum-cost flow problem.
Solution. Set the source supply \(b_s = 1\) and sink demand \(b_t = -1\), all other \(b_i = 0\), give each arc cost equal to its length and unlimited capacity. Sending the single unit from \(s\) to \(t\) at least cost forces it along the shortest path, and total unimodularity keeps the optimal flow \(0\)–\(1\) on each arc.
Chapter Summary
Nodes joined by arcs; a tree has \(n-1\) arcs and no cycle; a spanning tree reaches every node.
Dijkstra labels the nearest node permanently and relaxes its arcs — needs \(\ell_{ij} \ge 0\).
The greedy rule (Kruskal/Prim) adds cheapest cycle-free arcs; the cut property makes it optimal.
Ford–Fulkerson pushes flow along augmenting paths until none remains.
Max flow \(=\) min cut; the saturated cut is the network's bottleneck.
Supplies, costs, capacities; totally unimodular, so integer — solved by the network simplex.
Problems
Solve each on the appropriate network, showing the labels, arcs, or paths at each step. Difficulty rises down the list.
- Define node, arc, path, cycle, and spanning tree, and state how many arcs a spanning tree of \(n\) nodes has.
- Explain why Dijkstra's algorithm may give a wrong answer when some arc lengths are negative.
- Run Dijkstra from node 1 on the chapter network and give the shortest distance to every node, not just node 5.
- State the difference between the shortest-path problem and the minimum spanning tree problem in one sentence each.
- Apply Prim's algorithm to the chapter network starting from node 4 and confirm the same tree of length \(7\).
- State the cut property and use it to argue that the cheapest arc in a connected network is always in some MST.
- Define an augmenting path and the residual capacity of an arc, and explain why reverse residual arcs are needed.
- For the directed capacity network, list one \(s\)–\(t\) cut of capacity greater than \(5\) and explain why it is not the minimum.
- State the max-flow min-cut theorem and explain how the stopping condition of Ford–Fulkerson proves it.
- Write the minimum-cost flow formulation and show how setting all supplies and demands to \(1\) recovers the assignment problem.
- Explain why the node–arc incidence matrix being totally unimodular guarantees integer optimal flows.
- A courier network has source \(s\), sink \(t\), and arcs \(s\!\to\!a\,(5),\ s\!\to\!b\,(3),\ a\!\to\!b\,(2),\ a\!\to\!t\,(2),\ b\!\to\!t\,(5)\) with the numbers in parentheses as capacities. Find the maximum flow, the minimum cut, and verify they are equal.