Networks and routes in CAT DILR: shortest paths, route counts and flows

Network sets give you points (towns, junctions, stations) and links between them (roads, pipes, flights), each with a number attached: a distance, a time, a capacity. The questions ask for the best route, the number of routes, or how much can flow through the system.

These sets feel unfamiliar because most aspirants rarely practise them, but the methods are mechanical. The main risk is missing a route. This guide gives you a labelling method for shortest paths, the counting rule for grids, and the balance rule for flows, with every answer re-checked by listing all routes by computer.

Three kinds of network question

Shortest paths: the labelling method

For a small network, you can list routes. For anything with more than five or six points, listing misses routes. Label instead.

1. Give the start a label of 0.
2. From the point with the smallest fixed label, look at each neighbour. Its tentative label is the fixed label plus the link length. Keep the smaller if it already has one.
3. Fix the smallest tentative label in the network. Repeat from that point.
4. Stop when the destination is fixed. Trace back through the links that set each label.

This is Dijkstra's method, and on paper it takes a minute for a six-town network.

Worked set 1: six towns

Six towns, P, Q, R, S, T and U, are joined by two-way roads. No other roads exist.

Labelling from P.

Q1. What is the shortest distance from P to T? 21 km, by P–Q–R–U–T (6 + 2 + 7 + 6).

The shortest route uses four roads, while P–U–T uses only two and is 22 km. "Fewest roads" and "shortest distance" are different questions.

Q2. What is the shortest route from P to S? 18 km, by P–Q–R–S. The direct-looking P–R–S is 19 km.

Q3. If road R–U is closed, what is the shortest distance from P to T? Redo only what depended on R–U. U's best label becomes 16 (direct P–U), so T via U is 22. T via S is still 18 + 5 = 23. 22 km, by P–U–T.

Q4. A courier must pass through S on the way from P to T. What is the shortest such trip? P to S is 18, S to T is 5: 23 km, by P–Q–R–S–T.

Counting routes on a grid

On a grid where you may move only right or up, a route from one corner to another is a sequence of R and U steps. For 3 steps right and 2 up, choose which 2 of the 5 steps are "up": C(5, 2) = 10 routes.

For a 4-by-3 grid (4 right, 3 up), there are C(7, 3) = 35 routes.

Routes through a point. To pass through the point 2 right and 1 up from the start, multiply: routes to it, C(3, 1) = 3, times routes from it to the end (2 right, 2 up), C(4, 2) = 6. That gives 18.

Routes avoiding that point. Total minus through: 35 − 18 = 17.

When blocks are irregular, write the count at each point: every point's count is the sum of the counts at the point to its left and the point below it. A blocked point gets 0. This never misses a route.

Flows: balance at every junction

In a pipe or traffic network, whatever enters a junction leaves it. Only the source and the sink are exempt.

Worked set 2: a pipe network

Water flows from a source S to a tank T through junctions A and B. Pipes run S→A, S→B, A→B, A→T and B→T. The table gives each pipe's capacity in litres per minute.

Q1. In one setting, S sends 100 litres per minute, A→T carries 40 and S→B carries 40. Find the other flows.

• At S: S→A = 100 − 40 = 60.
• At A: 60 in, so A→B = 60 − 40 = 20.
• At B: 40 + 20 = 60 out on B→T.
• Check at T: 40 + 60 = 100. Every pipe is within capacity.

Q2. What is the maximum flow from S to T? Look for the narrowest "cut": a set of pipes whose removal separates S from T.

The smallest cut is 100, so no flow can exceed 100, and Q1's flow reaches it. The maximum is 100. A computer search over every whole-number flow agrees.

Common mistakes

• Stopping at the first route you find. Label, or list systematically; the obvious route is often not the shortest.
• Treating one-way links as two-way. Mark arrows on your diagram before starting.
• Counting grid routes by hand. Beyond small grids, use combinations or the point-by-point sums.
• Forgetting capacity limits after balancing. A balanced flow is valid only if each pipe stays within its capacity.

Practice set

1. In worked set 1, what is the shortest distance from Q to U?
2. In worked set 1, if road S–T is closed, what is the shortest distance from P to T?
3. On a grid with 3 steps right and 3 steps up, how many routes avoid the point 1 right and 1 up from the start?

Answers:

1. 9 km, by Q–R–U (2 + 7).
2. 21 km. The best route, P–Q–R–U–T, never used S–T.
3. 8. Total C(6, 3) = 20. Through the point: 2 ways to reach it (RU or UR) × C(4, 2) = 6 ways from it = 12. Avoiding: 20 − 12 = 8.

What to do next

• Run the labelling method on two networks this week, writing the step table each time.
• Practise grid counts with one blocked point, using both the subtraction and the point-by-point method.
• Solve one flow set and find its narrowest cut.
• Revisit arrangement sets for case discipline, and set selection to decide when a network set is worth opening.