Find shortest paths through weighted networks and determine the maximum flow using the minimum cut in a capacitated network.

What this dot point is asking

You must find the shortest path through a weighted network and find the maximum flow using the minimum-cut idea.

Shortest path in a weighted network

Each edge carries a weight (distance, time or cost). The shortest path between two vertices is the route whose edge weights sum to the smallest total. For small networks you list the sensible routes and total each, then pick the smallest.

Network flow: capacities, source and sink

In a flow network each directed edge has a capacity, the maximum it can carry. Flow enters at the source and leaves at the sink. The flow along any edge cannot exceed its capacity, and at every other vertex the flow in must equal the flow out (conservation of flow).

Finding the maximum flow

List the possible cuts, total the capacities of the forward edges crossing each cut, and the smallest of these totals is the maximum flow.

Interpreting the bottleneck

The minimum cut identifies the bottleneck: the set of edges that limits the whole network. Increasing capacity anywhere except across the minimum cut will not raise the maximum flow. To improve throughput, you must increase a capacity on the minimum cut.