I want to explain this algorithm through its very literal motivating story: imagine I am a postal carrier who must walk down every street on my route, deliver mail, and return to the post office, while covering the least total distance possible. The Chinese Postman Problem (CPP), also called the Route Inspection Problem, asks me to find the shortest closed walk in a graph that traverses every edge at least once. Unlike the Traveling Salesperson Problem, which is about visiting every node, this is about covering every edge — and that distinction is what makes it solvable in polynomial time rather than being NP-hard.
History and Background
The problem was first studied by the Chinese mathematician Meigu Guan (also transliterated as Kwan Mei-Ko) in 1962, which is why it carries the name “Chinese Postman Problem” in his honor. Guan showed how the problem connects to Euler’s classical work on the Seven Bridges of Königsberg (1736), which first established the conditions under which a graph has a closed walk traversing every edge exactly once (an Eulerian circuit). The insight that ties the two together — using Edmonds’ 1965 blossom algorithm for minimum-weight perfect matching — allowed the CPP to be solved efficiently for graphs that aren’t already Eulerian.
Problem Statement
I define the problem as: given a connected, weighted graph $G = (V, E)$, find a closed walk of minimum total weight that traverses every edge at least once, starting and ending at the same vertex.
Core Concepts
- Eulerian circuit: a closed walk that traverses every edge of a graph exactly once and returns to the starting vertex — this exists if and only if every vertex has even degree (for undirected graphs) and the graph is connected.
- Odd-degree vertex: a vertex with an odd number of incident edges — the presence of these is exactly what prevents a graph from having a “free” Eulerian circuit.
- Vertex degree: the number of edges incident to a vertex.
- Minimum-weight perfect matching: pairing up all odd-degree vertices such that the sum of the shortest-path distances between matched pairs is minimized.
- Edge duplication: the technique of adding duplicate copies of certain edges (along shortest paths between matched odd vertices) so that every vertex ends up with even degree, making an Eulerian circuit possible.
How It Works
- I check whether the graph is connected — if not, the problem has no valid solution in the classic formulation.
- I compute the degree of every vertex and identify the set of odd-degree vertices.
- If there are no odd-degree vertices, the graph is already Eulerian, and I simply find the Eulerian circuit directly (via Hierholzer’s algorithm, for instance) — this is my optimal route.
- If there are odd-degree vertices, I compute the shortest-path distance between every pair of them.
- I find a minimum-weight perfect matching over these odd-degree vertices, pairing them up to minimize total added distance.
- For each matched pair, I duplicate the edges along their shortest path in the original graph, which makes their degrees even.
- With every vertex now at even degree, the (multi-)graph is Eulerian, so I find its Eulerian circuit — that circuit is the postman’s optimal route.
Working Principle
The core logic hinges on a classical graph-theory fact: a connected graph has an Eulerian circuit if and only if every vertex has even degree. When some vertices have odd degree, I know I’ll be forced to re-traverse (duplicate) some edges to “fix” the parity, since every time I enter and leave a vertex it must be through a pair of edges — an odd-degree vertex, sooner or later, requires an extra pass. The problem then becomes: which edges should I duplicate, at minimum extra cost, to make every vertex even? That’s exactly a minimum-weight perfect matching problem on the odd-degree vertices, using shortest-path distances as matching costs.
Mathematical Foundation
A graph has an Eulerian circuit if and only if:
$$ \deg(v) \equiv 0 \pmod{2} \quad \text{for all } v \in V $$
The number of odd-degree vertices in any graph is always even, guaranteed by the handshake lemma:
$$ \sum_{v \in V} \deg(v) = 2|E| $$
If $O$ is the set of odd-degree vertices, I want the perfect matching $M$ on $O$ minimizing:
$$ \sum_{(u,v) \in M} d(u,v) $$
where $d(u,v)$ is the shortest-path distance between $u$ and $v$ in $G$. The total cost of the postman’s route is then:
$$ \text{Total Cost} = \sum_{e \in E} w(e) + \sum_{(u,v) \in M} d(u,v) $$
Diagrams
flowchart TD
Start([Start]) --> Degree[Compute vertex degrees]
Degree --> OddCheck{Any odd-degree vertices?}
OddCheck -- No --> Euler[Find Eulerian circuit directly]
OddCheck -- Yes --> Pairs[Compute shortest paths between odd vertices]
Pairs --> Match[Find minimum-weight perfect matching]
Match --> Dup[Duplicate matched shortest-path edges]
Dup --> Euler
Euler --> End([Return optimal postman route])Pseudocode
function ChinesePostman(Graph):
if Graph is not connected:
return "No solution: graph disconnected"
oddVertices = [v for v in Graph.vertices if degree(v) is odd]
if oddVertices is empty:
return EulerianCircuit(Graph)
// Build a complete graph over oddVertices with shortest-path weights
for each pair (u, v) in oddVertices:
distance[u][v] = ShortestPath(Graph, u, v)
matching = MinimumWeightPerfectMatching(oddVertices, distance)
for each (u, v) in matching:
path = ShortestPathEdges(Graph, u, v)
duplicate all edges in path within Graph
return EulerianCircuit(Graph)
Step-by-Step Example
Using the graph above: A–B(2), B–C(3), C–D(2), D–A(3), A–C(4).
- Degrees: A=3 (B, D, C), B=2 (A, C), C=3 (B, D, A), D=2 (C, A).
- Odd-degree vertices: A and C.
- Shortest path between A and C directly: the edge A–C has weight 4, but via A–B–C it’s 2+3=5, so the shortest path is the direct edge, distance 4.
- Only one pair to match: (A, C), so the matching is trivially {(A,C)} with cost 4.
- I duplicate edge A–C (weight 4).
- Now degrees: A=4, B=2, C=4, D=2 — all even, so an Eulerian circuit exists.
- Total route cost = sum of original edges (2+3+2+3+4=14) + duplicated edge (4) = 18.
- One valid route: A→B→C→D→A→C→A (traversing the duplicated A–C edge once extra), covering every original edge and returning to A.
Time Complexity
- Computing vertex degrees: $O(V + E)$.
- All-pairs shortest paths between odd vertices (using Dijkstra from each odd vertex, or Floyd–Warshall): $O(V \cdot (E + V \log V))$ or $O(V^3)$ respectively.
- Minimum-weight perfect matching (Edmonds’ blossom algorithm): $O(V^3)$ in general, though specialized implementations can do better.
- Eulerian circuit construction (Hierholzer’s algorithm): $O(E)$.
- Overall, the dominant cost is typically the matching step, giving roughly $O(V^3)$ total.
Space Complexity
I need $O(V^2)$ space to store pairwise shortest-path distances among odd vertices, $O(V+E)$ for the graph itself (which grows slightly after edge duplication), and $O(V)$ for degree tracking and matching state — overall space is $O(V^2)$, dominated by the distance matrix among odd vertices.
Correctness Analysis
The correctness rests on two established theorems: first, Euler’s theorem guarantees that a connected graph admits a closed walk traversing every edge exactly once if and only if all vertices have even degree. Second, since the number of odd-degree vertices is always even (by the handshake lemma), they can always be perfectly paired. Minimizing the total distance of duplicated paths directly minimizes the extra distance the postman must re-walk, because every unit of “extra” distance in the optimal solution corresponds to exactly one edge being traversed more than once, and those redundant traversals must connect odd-degree vertices in pairs to restore even parity — which is precisely what minimum-weight perfect matching optimizes.
Advantages
- Solvable in polynomial time, unlike the closely related but NP-hard Traveling Salesperson Problem.
- Guarantees a truly optimal (minimum-distance) solution, not just a heuristic approximation.
- Directly models many real-world “cover every edge” logistics problems.
- Builds on well-understood classical results (Euler’s theorem, matching theory), making it mathematically well-grounded.
Disadvantages
- The minimum-weight perfect matching step, while polynomial, is relatively complex to implement correctly (Edmonds’ blossom algorithm is notoriously intricate).
- Directed and mixed (some directed, some undirected edges) versions of the problem are significantly harder — the mixed CPP is actually NP-hard.
- Assumes the graph is connected; disconnected service regions require separate treatment.
- Real-world constraints like one-way streets, turn restrictions, and time windows aren’t captured by the basic model.
Applications
- Mail delivery and package courier route planning (its namesake application).
- Street sweeping, snow plowing, and garbage collection route optimization.
- Meter reading and utility inspection routes.
- Network cable/pipeline inspection where every segment must be checked.
- Printed circuit board testing, where every trace must be probed.
Implementation in C
#include <stdio.h>
#include <limits.h>
#include <stdbool.h>
#define V 4 // A=0, B=1, C=2, D=3
#define INF INT_MAX
// Simple Floyd-Warshall to get all-pairs shortest paths
void floydWarshall(int dist[V][V]) {
for (int k = 0; k < V; k++)
for (int i = 0; i < V; i++)
for (int j = 0; j < V; j++)
if (dist[i][k] != INF && dist[k][j] != INF &&
dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}
int main() {
int graph[V][V] = {
{0, 2, 4, 3},
{2, 0, 3, INF},
{4, 3, 0, 2},
{3, INF, 2, 0}
};
int degree[V] = {0};
int totalWeight = 0;
// Compute degrees and total edge weight (count each undirected edge once)
for (int i = 0; i < V; i++) {
for (int j = i + 1; j < V; j++) {
if (graph[i][j] != INF && graph[i][j] != 0) {
degree[i]++;
degree[j]++;
totalWeight += graph[i][j];
}
}
}
printf("Vertex degrees:\n");
int oddVertices[V], oddCount = 0;
for (int i = 0; i < V; i++) {
printf("Vertex %d: degree %d\n", i, degree[i]);
if (degree[i] % 2 != 0) oddVertices[oddCount++] = i;
}
int dist[V][V];
for (int i = 0; i < V; i++)
for (int j = 0; j < V; j++)
dist[i][j] = graph[i][j];
floydWarshall(dist);
// For this small example (exactly 2 odd vertices), the matching is trivial
int extra = 0;
if (oddCount == 2) {
extra = dist[oddVertices[0]][oddVertices[1]];
printf("Odd vertices %d and %d matched, extra distance = %d\n",
oddVertices[0], oddVertices[1], extra);
} else if (oddCount > 0) {
printf("More than 2 odd vertices — requires full minimum-weight matching.\n");
}
printf("Total edge weight: %d\n", totalWeight);
printf("Optimal postman route cost: %d\n", totalWeight + extra);
return 0;
}
Sample Input and Output
Input: the graph above (A, B, C, D with the given edge weights).
Output:
Vertex degrees:
Vertex 0: degree 3
Vertex 1: degree 2
Vertex 2: degree 3
Vertex 3: degree 2
Odd vertices 0 and 2 matched, extra distance = 4
Total edge weight: 14
Optimal postman route cost: 18
This matches my manual walkthrough.
Optimization Techniques
- For graphs with more than two odd vertices, use an efficient blossom algorithm implementation (e.g., from a well-tested library) rather than a naive brute-force matching, since brute force is factorial in the number of odd vertices.
- Precompute all-pairs shortest paths once with Floyd–Warshall or repeated Dijkstra runs, rather than recomputing per matching candidate.
- For very large road networks, restrict the shortest-path and matching computation to just the odd-degree vertices rather than the full vertex set.
- Use Hierholzer’s algorithm (linear time) rather than a naive edge-by-edge search for constructing the final Eulerian circuit.
Common Mistakes
- Forgetting that the number of odd-degree vertices is always even — if an implementation finds an odd count, there’s a bug in degree counting.
- Applying the undirected CPP algorithm directly to a directed or mixed graph, where the matching and balance conditions are entirely different.
- Confusing the Chinese Postman Problem (cover every edge) with the Traveling Salesperson Problem (visit every vertex) — they require fundamentally different algorithms and complexity classes.
- Not verifying graph connectivity first, which can cause the algorithm to silently produce an incomplete or nonsensical route.
Further Reading
- Guan, M. (1962). “Graphic Programming Using Odd or Even Points.” Chinese Mathematics, 1, 273–277.
- Edmonds, J. (1965). “Paths, Trees, and Flowers.” Canadian Journal of Mathematics, 17, 449–467.
- Edmonds, J., & Johnson, E. L. (1973). “Matching, Euler Tours and the Chinese Postman.” Mathematical Programming, 5(1), 88–124.
- GeeksforGeeks, Chinese Postman/Route Inspection Problem: https://www.geeksforgeeks.org/dsa/route-inspection-or-chinese-postman-algorithm/
