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.