The route inspection problemEdexcel International A Level Maths: Revision notes

Some jobs need every road to be travelled: a postal worker, a gritting lorry or a street cleaner. The route inspection problem, also called the Chinese postman problem, asks for the shortest route around a network that travels along every arc at least once and finishes at the start vertex. If the network can be travelled using each arc exactly once and returning to the start, the shortest route is just the sum of all the arc lengths. Otherwise some arcs must be travelled twice, and the aim is to repeat the least possible length.

The order (or degree) of a vertex is the number of arcs meeting at it. A vertex is odd if its order is odd, and even if its order is even. A closed route that uses each arc once needs every vertex to be even. This is because each time the route enters a vertex it must leave again, using up arcs in pairs. Any network has an even number of odd vertices (never 1 or 3). In this subtopic there are $0$, $2$ or $4$ odd vertices. If all vertices are even, the shortest route has length equal to the total weight of the arcs.

1. Find the order of every vertex and list the odd vertices.
2. If there are none, the route length is the total weight of the arcs.
3. Otherwise pair up the odd vertices in every possible way.
4. For each pairing find the shortest path between the two vertices in each pair, using inspection (the shortest path may go through other vertices) and add the lengths.
5. Choose the pairing with the least total.
6. The shortest route length is the total weight of the arcs plus this least total. The arcs on the chosen paths are the ones travelled twice. For $2$ odd vertices there is just one pairing. For $4$ odd vertices $P$, $Q$, $R$, $S$ there are $3$ pairings: $PQ+RS$, $PR+QS$ and $PS+QR$. Floyd's algorithm is not needed.

Streets $AB=5$, $AC=8$, $BC=4$, $BD=7$, $CD=6$, $CE=9$, $DE=3$. The orders are $A$: 2, $B$: 3, $C$: 4, $D$: 3, $E$: 2, so $B$ and $D$ are odd. The shortest path from $B$ to $D$ is $BD=7$, as $B$-$C$-$D$ is $10$. Total of arcs $=5+8+4+7+6+9+3=42$. Shortest route $=42+7=49$, with $BD$ travelled twice.

State the odd vertices, show all the pairings, give their totals 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. If a new arc joins two odd vertices, both become even, so the number of odd vertices falls by $2$. If it joins an odd vertex to an even vertex, the even vertex becomes odd, so the number of odd vertices is unchanged. Re-do the pairing with the new odd vertices, and compare the new route length with the old one to form an inequality for the new arc's length. The start vertex is the end vertex, so the length does not depend on where you start.