Shortest path and network flow (SACE Stage 2 General Mathematics)
“Find shortest paths through weighted networks and determine the maximum flow using the minimum cut in a capacitated network.”
A shortest-path problem finds the least-weight route between two vertices by comparing the totals of possible paths. A network-flow problem finds the greatest flow from source to sink, which equals the capacity of the minimum cut (the maximum-flow minimum-cut theorem).
Jump to a section
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.
A network in which each edge is labelled with a numerical weight such as distance, time or cost. The length of a path is the sum of the weights of its edges, and the shortest path is the path of least total length between two chosen vertices.
Shortest route by inspection
A delivery network from S to T has routes: S-A-T with weights 4 and 7; S-B-T with weights 3 and 9; S-A-B-T with weights 4, 2 and 9. Find the shortest path.
Total each route:
- S-A-T:
- S-B-T:
- S-A-B-T:
The smallest total is 11, so the shortest path is S-A-T with length 11.
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).
A cut separates the source from the sink by removing edges; its capacity is the sum of the capacities of the cut edges that carry flow towards the sink. The maximum possible flow from source to sink equals the capacity of the minimum cut.
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.
Finding maximum flow from a cut
Water flows from source S to sink T. The pipes leaving S have capacities 6 and 5 (total 11). The pipes entering T have capacities 4 and 8 (total 12). A middle cut across the network sums to 9. Find the maximum flow.
The candidate cut capacities are 11 (at the source), 12 (at the sink) and 9 (across the middle). The minimum cut is the smallest of these:
So at most 9 units can flow from S to T per period; the middle of the network is the bottleneck.
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.
When totalling a cut, add the capacities of edges that go from the source side to the sink side. Edges pointing back the other way do not add to the cut capacity. Counting backward edges inflates the total and hides the true bottleneck.
Do not assume the route with the fewest edges is the shortest path; a path with more edges can have a smaller total weight. For flow problems, do not report the largest cut as the answer; the maximum flow equals the minimum cut, so you take the smallest cut capacity, not the largest.
Exam-style questions
Questions in the style of SACE Board exam questions on this dot point, each with a worked answer. They are written by ExamExplained unless tagged "Past paper"; the year shows the paper a question is modelled on.
SACE 2022-style3 marksCalculator-assumed. A delivery network from to has routes S-A-T with weights 4 and 7, S-B-T with weights 3 and 9, and S-A-B-T with weights 4, 2 and 9. Find the shortest path and its length.Show worked answer →
Total each route: S-A-T ; S-B-T ; S-A-B-T .
The smallest total is 11, so the shortest path is S-A-T with length 11.
Marks: two for totalling the candidate routes, one for identifying S-A-T as shortest. Note the fewest-edge route is not always the shortest.
SACE 2023-style2 marksCalculator-assumed. In a flow network from source to sink , the cut at the source totals 11, the cut at the sink totals 12, and a middle cut totals 9. State the maximum flow and identify the bottleneck.Show worked answer →
By the maximum-flow minimum-cut theorem, the maximum flow equals the smallest cut capacity:
So at most 9 units can flow from to per period, and the middle cut is the bottleneck. Marks: one for taking the minimum cut, one for identifying the bottleneck.