Wait, What?
Sometimes the shortest route is not about visiting every place. It is about traversing every required edge—and paying as little as possible for the repeats.
The Chinese Postman Problem, also called the Route Inspection Problem, asks for the shortest closed walk that traverses every edge of a connected weighted graph at least once. It is a natural model for street sweeping, snow ploughing, inspection, waste collection and any task whose obligations live on links rather than just locations. The undirected case has an elegant solution: identify odd-degree vertices, connect them in pairs as cheaply as possible, duplicate those shortest paths, then take an Euler tour.
Quick Answer
Learn the Chinese Postman algorithm through Euler tours → degree parity → odd vertices → all-pairs shortest paths among odd vertices → minimum-weight perfect matching → edge duplication → Hierholzer traversal → route reconstruction → directed/mixed variants → operational constraints. The invariant is that every closed walk enters and leaves each vertex an even number of times, so an Eulerian route becomes possible exactly after the odd-degree defects are repaired.
1. Start With Euler Before Optimisation
A connected undirected graph has an Euler circuit if and only if every vertex has even degree. If that condition already holds, the Chinese Postman problem is easy: traverse every edge exactly once using an Euler-tour algorithm such as Hierholzer’s.
This is the Learning Hall boundary: the existing Hierholzer article owns how to construct an Euler tour once an Eulerian graph exists. The Chinese Postman article owns how to modify a non-Eulerian weighted graph as cheaply as possible so an optimal closed inspection route exists.
2. Why Odd Degrees Cause Repetition
In any closed walk, every time you enter a vertex you must eventually leave it. Edge uses therefore contribute an even total incidence at each vertex. If the original graph has odd-degree vertices, some edges must be repeated so that the multigraph formed by counting traversals has even degree everywhere.
The handshaking lemma guarantees that the number of odd-degree vertices is even. That fact is what makes pairing possible.
3. The Problem Becomes: Which Odd Vertices Should Be Paired?
Suppose the odd-degree set is O={v₁,…,v₂k}. Duplicating a path between two odd vertices flips the parity of both endpoints while intermediate vertices gain degree 2 and remain unchanged in parity. Therefore, if we pair all odd vertices and duplicate one connecting path for each pair, every vertex becomes even.
But different pairings have different costs. The optimization task is to choose the pairing whose duplicated paths have minimum total weight.
4. Convert the Graph Into a Matching Problem
Build a complete auxiliary graph on the odd vertices. The weight between odd vertices u and v is the length of the shortest path between u and v in the original graph. Then compute a minimum-weight perfect matching in this auxiliary graph.
odd = vertices with odd degree
D = shortest-path distances among odd vertices
M = minimum_weight_perfect_matching(odd, weights=D)
for each matched pair (u,v) in M:
duplicate the edges on one shortest u-v path
return Euler circuit of the augmented multigraphThis reduction is the core insight of the undirected algorithm.
5. Work a Small Graph by Hand
Imagine a connected weighted graph with four odd vertices A, B, C and D. Suppose shortest-path distances are:
d(A,B)=4 d(A,C)=6 d(A,D)=7
d(B,C)=5 d(B,D)=3 d(C,D)=4There are only three perfect matchings:
- (A,B)+(C,D): cost 4+4=8
- (A,C)+(B,D): cost 6+3=9
- (A,D)+(B,C): cost 7+5=12
The minimum pairing is therefore (A,B) and (C,D). Duplicate the actual shortest A–B path and C–D path in the original graph. The new multigraph has even degree at every vertex. Hierholzer can then produce an Euler circuit whose total length is the weight of all original edges plus 8.
6. Why Shortest Paths Are Enough
Once we decide that u and v should be paired, any duplicated walk connecting them changes parity correctly. Choosing anything longer than a shortest path would add unnecessary cost. Therefore the pairing can be solved purely on the metric closure of the odd vertices.
This separation is useful professionally: shortest-path computation solves the connection cost; matching solves the global pairing choice; Euler traversal solves the route extraction.
7. The Proof Skeleton
A clean optimality argument has two directions:
- Any closed postman tour induces additional edge traversals whose odd-incidence endpoints must pair up the original odd vertices.
- Replacing each such connecting walk by a shortest path cannot increase cost, so some optimal solution corresponds to a pairing of odd vertices using shortest-path distances.
Therefore a minimum-weight perfect matching gives the least possible added cost. After duplicating those paths, the graph is Eulerian, and an Euler circuit realizes that optimum.
8. Complexity Depends on the Number of Odd Vertices
Let n=|V|, m=|E| and let 2k be the number of odd vertices. The algorithm needs shortest paths among odd vertices and a minimum-weight perfect matching on 2k vertices. On sparse nonnegative graphs, repeated Dijkstra runs are common; if k is small relative to n, this can be efficient. The matching stage can dominate when many vertices are odd.
The final Euler traversal is linear in the size of the augmented multigraph.
9. Reconstruct the Route, Not Just the Cost
A common implementation mistake is to compute matching distances but forget the actual shortest-path predecessors. You need the path edges so that the augmented multigraph contains the correct duplicated edges before running Hierholzer. Store predecessor trees or rerun shortest-path reconstruction for matched pairs.
10. Multigraphs Are Normal Here
After duplication, the same original edge may appear multiple times. The correct data structure is therefore a multigraph or an edge list where parallel copies have distinct traversal identities. If an implementation collapses duplicate edges into one, the Euler traversal can fail or return the wrong route.
11. Directed Chinese Postman Is a Different Balancing Problem
In a strongly connected directed graph, Eulerian balance requires indegree(v)=outdegree(v) at every vertex. The directed postman problem repairs imbalance by sending additional flow along shortest directed paths. This leads to a minimum-cost flow formulation rather than the undirected odd-vertex matching formulation.
Mixed, windy and rural postman problems introduce further complications. Some variants are much harder computationally. Do not generalize the elegant undirected algorithm beyond its contract.
12. Real Routes Have More Than Edge Length
Operational routing may include one-way streets, turn penalties, depot constraints, service times, road restrictions, time windows, vehicle capacities or required subsets of edges. Once those constraints appear, the classical Chinese Postman model becomes a baseline rather than a complete solution.
A professional modeller should state clearly what each edge weight means: distance, time, energy, money, risk or a composite cost.
13. How to Learn It Efficiently
Start with parity before code. Draw a graph, circle all odd-degree vertices, and predict how duplicating a path changes endpoint parity. Then calculate the tiny matching by hand. Run a reference implementation. Investigate the augmented multigraph. Only after that should you automate shortest paths and matching. This sequence exposes the reduction instead of hiding it behind a library call.
Common Failure States
- Solving a travelling-salesperson problem when the obligation is to traverse edges rather than visit vertices.
- Pairing odd vertices using direct edge weights instead of shortest-path distances.
- Using greedy nearest-neighbour pairing and assuming it is globally optimal.
- Forgetting to reconstruct and duplicate the matched shortest paths.
- Collapsing parallel edges in the augmented multigraph.
- Running Hierholzer before all vertex degrees are even.
- Applying the undirected matching solution unchanged to directed or mixed graphs.
Practice Ladder
- Beginner: identify Eulerian and non-Eulerian graphs by degree parity.
- Foundation: repair graphs with exactly two odd vertices by duplicating one shortest path.
- Intermediate: solve four- and six-odd-vertex examples with an explicit matching table.
- Advanced: implement shortest-path reconstruction, minimum-weight perfect matching and multigraph Euler traversal end to end.
- Professional: model a real street-inspection network and compare the classical solution with variants that add direction, turn penalties, depot requirements or partial edge service.
Learning Hall Boundary
This article owns closed edge-inspection optimization on connected weighted undirected graphs through parity repair and minimum-weight matching. It does not replace Hierholzer’s Euler traversal, shortest-path algorithms, assignment matching, minimum-cost flow or vehicle-routing material.
Evidence Boundary
The Chinese Postman Problem was introduced by Kwan Mei-Ko in the early 1960s. Jack Edmonds and Ellis L. Johnson’s 1973 paper “Matching, Euler tours and the Chinese postman” established the matching-based polynomial treatment that became the canonical undirected formulation. Modern graph libraries typically implement the solution by combining shortest paths, matching and Eulerian augmentation.
Professional rule: you understand the Chinese Postman algorithm when you can explain why parity is the obstacle, why odd vertices must be paired, why shortest-path metric closure is valid, and why the minimum matching cost is exactly the unavoidable extra route cost.
