Maths › Decision Mathematics 1 › Route inspection
Route inspection
Walk along every road and come back to where you started. If the network has odd nodes some roads must be walked twice, and the whole problem is choosing which ones.
Builds on Shortest paths: Dijkstra and Floyd and Graphs: order, Eulerian paths and planarity.
IN THIS TOPIC
- Identify the odd nodes and list every possible pairing of them.
- Find the shortest path between each pair and choose the cheapest pairing.
- State the length of the shortest closed route and which edges are repeated.
- Adapt the method when the route need not return to the start.
COMMON MISCONCEPTION
In route inspection you repeat the shortest edges in the network until every node has even order.
Why anything has to be repeated
A closed route using every edge exactly once exists only when every node has even order, since each visit to a node uses two of its edges. Odd nodes therefore force repetition, and repeating an edge amounts to adding a duplicate, which raises the order of both its ends by one.
So the job is to pair up the odd nodes and repeat a shortest path between each pair. Shortest path, not shortest edge. The shortest path between two odd nodes may run through several edges and past other nodes, and repeating an edge between two even nodes would only make matters worse by turning them odd.
WORKED EXAMPLE
Choosing the pairing
The network's odd nodes are A, B, D and E, with shortest paths AB 5, AD 9, AE 13, BD 7, BE 9, DE 9. Find the cheapest pairing.
There are three ways to pair four nodes.
AB with DE: 5 + 9 = 14.
AD with BE: 9 + 9 = 18. AE with BD: 13 + 7 = 20.
The cheapest is AB and DE, adding 14 to the route.
The answer
The length of the shortest closed route is the total weight of all the edges plus the cost of the cheapest pairing. Four odd nodes give three pairings, and the specification caps the number of odd nodes at four for that reason; six nodes would give fifteen pairings.
Two variations come up. With no odd nodes, nothing is repeated and the answer is simply the total weight. If the route need not return to the start, leave two odd nodes unpaired to be the ends of the walk, pair the rest as cheaply as you can, and start and finish at the two left over. Choosing which two to leave out is then the decision, and the pair with the longest shortest path between them is usually the right choice.
GUIDED PRACTICE
The full answer
The nine edges of the network total 55. Find the length of the shortest closed route travelling along every edge at least once, and say which edges are repeated.
Show the working
The cheapest pairing costs 14.
Total = 55 + 14 = 69.
The repeated edges are AB, and the shortest D to E path, which is D to C to E.
So DC and CE are each walked twice, as is AB, and every other edge exactly once.
ASSESSMENT FOCUS
- List the odd nodes first. If there are none, the answer is the total weight and nothing is repeated.
- Write out all three pairings with their costs, even the ones you can see are worse.
- Use shortest paths between odd nodes, which may pass through other nodes.
- State the repeated edges as well as the total. The question almost always asks.
CHECK YOURSELF
A network of total weight 80 has odd nodes P, Q, R, S with shortest paths PQ 6, PR 9, PS 11, QR 8, QS 5, RS 7. Find the shortest closed route.
Show a hint
Three pairings; take the cheapest.
Show the answer
PQ + RS = 13, PR + QS = 14, PS + QR = 19. Cheapest is 13, so the route is 80 + 13 = 93.
Odd nodes force repetition, so pair them up and repeat a shortest path between each pair.
The answer is the total weight of the network plus the cost of the cheapest pairing, and the repeated edges must be named.
WORKBOOK
Printable practice for this topic: original exam-style questions with room to work, and a fully worked answer book. Free to use; please do not redistribute or sell.
Or read them with their worked answers on the route inspection questions page.
CHECK YOUR PROGRESS
Rate how confident you feel with each objective for this lesson. Ratings are saved in this browser, on this device, unless you sign in.
- Identify the odd nodes and list every possible pairing of them.
- Find the shortest path between each pair and choose the cheapest pairing.
- State the length of the shortest closed route and which edges are repeated.
- Adapt the method when the route need not return to the start.
Open the full revision checklist to see every objective in the course in one place.