Route Inspection Problem (Chinese Postman)

The route inspection problem (also called the Chinese Postman problem) asks: what is the minimum total weight of a closed walk that traverses every edge of a graph at least once? This models situations like a postal worker who must walk along every street and return to the start.

---

Key Observation

If the graph is Eulerian (all vertices have even degree), then an Eulerian circuit exists — a closed walk that uses every edge exactly once. The minimum total weight is simply the sum of all edge weights.

If the graph is not Eulerian, some edges must be traversed more than once. The algorithm finds the most efficient way to duplicate edges.

---

The Algorithm

Step 1: Find all odd-degree vertices.

By the handshaking lemma, there is always an even number of odd-degree vertices.

Step 2: Find the shortest paths between all pairs of odd-degree vertices.

Use Dijkstra's algorithm (or inspection for small graphs) to find the shortest distances.

Step 3: Find the minimum weight perfect matching.

Pair up the odd-degree vertices so that the total weight of the pairings (using shortest path distances) is minimised. For 2 odd vertices, there is only one pairing. For 4, there are 3 possible pairings. For 6, there are 15.

Step 4: Add the edges of the shortest paths for each matched pair.

This duplicates those edges, making all vertices even degree.

Step 5: Find an Eulerian circuit in the augmented graph.

The minimum total weight is the sum of all original edges plus the weight of the duplicated edges.

---

Worked Example

A graph has vertices A, B, C, D, E with edges:

Edge	Weight
AB	3
AC	5
BC	2
BD	4
CD	6
DE	3

Degrees: A = 2, B = 3, C = 3, D = 3, E = 1.

Wait — degree of E = 1 (only DE), degree of D = 3 (BD, CD, DE). Odd-degree vertices: B(3), C(3), D(3), E(1).