Chinese Postman Problem

The Chinese Postman Problem (also called Route Inspection) asks for the shortest closed walk that travels every edge of a graph at least once and returns to the start. It is the natural cousin of the Traveling Salesman, but about edges instead of vertices — and unlike TSP it is solvable in polynomial time.

The slow way first

If every vertex already had an even degree, the answer would just be the sum of all edge weights — a graph with all-even degrees has an Euler circuit, a closed walk that uses every edge exactly once with zero repetition. No street is ever retraced, so you pay each one exactly once.

The trouble is the odd-degree vertices. You enter and leave a vertex in pairs, so a vertex you visit an odd number of half-times forces you to retrace some street. Trying every possible set of retraced streets is exponential, so we need the structure underneath.

The idea: make every vertex even by duplicating cheap paths

There is a clean theorem: a connected graph has an even number of odd-degree vertices, and you can always pair them up. For each pair, duplicating the shortest path between them flips both endpoints to even degree. Choosing the pairing that minimizes total duplicated distance — a minimum-weight perfect matching on the odd vertices — gives exactly the extra distance the postman must pay. After duplication every vertex is even, so an Euler circuit exists.

So the answer is always sum(all edges) + (cheapest set of duplicated paths to even out the odd vertices).

Walk through it

Step through the animation. First we sum the five streets: 4 + 2 + 3 + 5 + 1 = 15. Then we read off the degrees — A=3, B=3, C=2, D=2 — and the odd vertices light up red: A and B. There is just one odd pair, so the matching is forced: duplicate the cheapest A-to-B path, which costs 4. We add that and walk the now-even graph as an Euler circuit. Final answer: 15 + 4 = 19.

Pseudocode

total = sum of every edge weight
compute degree of each vertex
odd = list of vertices whose degree is odd
if odd is empty:
    return total                      # graph is already Eulerian
dist = all-pairs shortest paths
extra = minimum-weight perfect matching of the odd vertices, using dist
return total + extra

The Python solution

def chinese_postman(n, edges):
    total = sum(w for _, _, w in edges)
    deg = degrees(n, edges)
    odd = [v for v in range(n) if deg[v] % 2 == 1]
    if not odd:
        return total                 # already Eulerian
    dist = all_pairs_shortest(n, edges)
    extra = min_weight_matching(odd, dist)
    return total + extra

• total is the sum of all edge weights — the unavoidable floor, since every street is walked at least once.
• deg holds each vertex degree; odd collects the vertices with an odd degree, the only ones that block an Euler circuit.
• If there are no odd vertices the graph is already Eulerian, so total itself is the answer.
• dist is the all-pairs shortest-path table, so a matched pair can be joined by their cheapest route (not just a direct edge).
• min_weight_matching pairs the odd vertices to minimize total duplicated distance; adding extra makes every vertex even and yields the optimal route.

Complexity

The odd-vertex count k is usually small, but the matching is the conceptually hard part. Everything else is standard shortest-path work, which keeps the whole problem polynomial — the key contrast with the NP-hard Traveling Salesman.

When this pattern shows up

Practice