The route inspection problem
Studying this course? Keep your progress in one place.
Key facts
- The route inspection problem (Chinese postman) asks for the shortest closed route that travels along every arc at least once.
- The order (degree) of a vertex is the number of arcs meeting at it; the number of odd vertices is always even.
- If every vertex is even, the shortest route is the total weight of all the arcs.
- Otherwise pair up the odd vertices in every way, find the shortest path in each pair, and add the least total to the arc total.
- Four odd vertices give three pairings; two odd vertices give one.
What the problem asks
A postal worker or gritting lorry must travel along every arc at least once and finish at the start; the aim is to repeat as little as possible.
Some jobs need every road to be travelled: a postal worker, a gritting lorry or a street cleaner. The route inspection problem, or Chinese postman problem, asks for the shortest route that travels along every arc at least once and finishes at the start vertex.
If every arc can be used exactly once, the shortest route is the sum of all the arc lengths. Otherwise some arcs must be travelled twice, and the aim is to repeat the least possible length.
A route inspection route must...
Odd and even vertices
The order of a vertex is the number of arcs meeting at it. A closed route using each arc once needs every vertex even.
The order (degree) of a vertex is the number of arcs meeting at it. A vertex is odd or even according to its order.
A closed route using each arc once needs every vertex to be even, because each time the route enters a vertex it must leave again, using arcs in pairs.
Any network has an even number of odd vertices. Here there are 0, 2 or 4.
No odd vertices
- Route length = total weight of arcs
2 odd vertices
- One way to pair them
4 odd vertices
- Three ways to pair them
A network has 5 arcs. What is the sum of the orders of all its vertices?
The algorithm
Pair the odd vertices in every possible way, find the shortest path for each pair, and repeat the arcs of the pairing with the least total.
For 2 odd vertices there is one pairing. For 4 odd vertices , , , there are 3 pairings: , and .
Find each shortest path by inspection. It may pass through other vertices.
Floyd's algorithm is not needed.
- 1
List odd vertices
find the order of every vertex
- 2
None odd?
the route length is the total weight of the arcs
- 3
Pair them up
in every possible way
- 4
Shortest paths
find the shortest path in each pair by inspection and add the lengths
- 5
Choose
take the pairing with the least total
- 6
Add
route length = total of arcs + least total
How many different ways are there to pair up 4 odd vertices?
Worked example
Only B and D are odd, so repeat the shortest path between them, BD = 7, and add it to the total of the arcs.
Streets are , , , , , and .
The orders are : 2, : 3, : 4, : 3, : 2, so and are the odd vertices.
There is only one pairing. The shortest path from to is , since -- is 10.
- Total of arcs
- Repeat shortest path BD7
- Route length
Worked example
Find the length of the shortest route that travels along every street and returns to its start.
- 1
The orders are : 2, : 3, : 4, : 3, : 2, so and are odd.
- 2
There is one pairing: with . The shortest path from to is , as -- is .
- 3
Total of arcs .
In the example, which arc is travelled twice?
Exam skills and modifying networks
State the odd vertices, show every pairing and its total, and say which arcs are repeated; these are method marks.
The route length is always at least the total weight of the arcs, so a smaller answer shows an error.
To modify a network, add the new arc and re-do the pairing with the new odd vertices. Compare the new route length with the old one to form an inequality for the new arc's length.
The route is closed, so the length does not depend on where you start.
- 1
List the odd vertices
there are always an even number
- 2
Show every pairing
with the shortest path and total for each
- 3
Choose the smallest total
say which arcs are repeated
- 4
Route length
total weight of all arcs plus the repeated total
New arc joins two odd vertices
- Both become even
- Odd vertices fall by 2
New arc joins odd to even
- Even vertex becomes odd
- Number of odd vertices unchanged
A new arc joins two vertices that are both odd. How many odd vertices are there now, if there were 4 before?
Try an exam question
A network has arcs PQ = 10, PR = 5, QR = 6, QS = 9, RS = 7 and ST = 4. Find the length of the shortest route that travels along every arc at least once and returns to its start. Show the pairings you considered.
[4 marks]
- [1]The odd vertices are Q, R, S and T.
- [1]Pairings: QR + ST = 6 + 4 = 10, QS + RT = 9 + 11 = 20, QT + RS = 13 + 7 = 20.
- [1]The least repeat is QR and ST, with length 10.
- [1]The arcs total 41, so the route length is 41 + 10 = 51.
That's the notes covered.
Carry on to the next subtopic.
Try a question
How many junctions have an odd number of streets meeting at them?
1 mark, marked against the mark scheme
How many junctions have an odd number of streets meeting at them?
1 mark, marked against the mark scheme