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.

Why minimum cut equals maximum flow

The maximum-flow minimum-cut theorem is intuitive once you see it as a bottleneck argument. Any cut separating the source from the sink must carry the entire flow across it, so no cut can carry less than the total flow - the flow is therefore limited by the smallest-capacity cut. Conversely, it can be shown that flow can always be increased until it saturates that smallest cut. The smallest cut is thus both an upper limit and an achievable target, which is why the maximum flow equals the minimum cut. To improve a network's throughput you must add capacity on a minimum-cut edge; adding it elsewhere leaves the bottleneck untouched.

Systematic shortest-path methods

For small networks, listing and totalling routes by inspection is enough, but for larger ones a systematic labelling method assigns each vertex the shortest distance found so far from the source, updating it whenever a shorter route is discovered. Working outward from the source, you finalise the nearest unvisited vertex at each step until the destination is reached. The same idea answers "shortest" whether the weights represent distance, time or cost, and SACE may present the network as a table of edge weights rather than a diagram, so being comfortable reading either form is important.

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.