Overview
The Chinese Postman Algorithm solves the route inspection problem by augmenting an Eulerian traversal problem with shortest paths or matching-like choices so every edge can be covered with minimum extra cost.
ExtendedSource checked
Chinese Postman Algorithm
Finds a minimum-cost closed walk that traverses every edge of a graph.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Optimization
- Difficulty
- Advanced
- Family
- Route inspection
- Tier
- Extended
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 0
- Relationships
- 2
- Code example
- Not ready
- Visualization
- Not ready
- Aliases
- Route Inspection Problem
Core Concepts
Eulerian traversaledge coveringminimum-cost augmentationroute inspection
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
Polynomial for standard weighted graph variants
Average
Polynomial; commonly dominated by shortest paths and matching-style augmentation
Worst
Polynomial for standard weighted graph variants
Space
O(n + m) plus augmentation structures
When to Use
- Use when every edge must be traversed at least once at low total cost.
When Not to Use
- Do not use when the task is visiting every vertex once; that is a traveling-salesperson-style problem.
What It Does
- Identifies graph vertices that prevent an Eulerian tour.
- Adds minimum-cost duplicated paths or pairings where needed.
- Constructs a closed route that traverses every edge.
Use Cases
- Street sweeping
- Postal route planning
- Inspection routing
Inputs
- A connected weighted graph whose edges must all be traversed.
Outputs
- A minimum-cost closed walk that traverses every edge at least once.
Pseudocode
- 1.Find non-Eulerian vertices.
- 2.Choose minimum-cost augmenting paths or pairings.
- 3.Build an Eulerian tour in the augmented graph.
Canonical Example
- Input
- A weighted connected graph representing streets.
- Output
- A closed walk that covers every street edge.
- Explanation
- Extra traversals are added only where needed to make an Eulerian closed walk possible.
Implementation Notes
- Undirected weighted cases are commonly reduced through odd-degree vertex pairing and Euler tour construction.
Common Pitfalls
- Confusing edge-covering routes with shortest paths between two endpoints.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationShow odd-degree vertices, duplicated augmenting paths, and the final Eulerian closed walk.
Step 1 of 3: Find non-Eulerian vertices.
graph-routeNotes
Variant details matter: undirected, directed, and mixed Chinese Postman formulations use different reductions and augmentation steps.
Sources (2)
What each reference supports for this entry.
Edmonds and Johnson (1973)
PaperSupports the Chinese Postman Problem algorithmic treatment through matching, Euler tours, and route-inspection structure.
Open sourceIBM Research publication record
DocumentationInstitutional publication metadata for Edmonds and Johnson's matching, Euler tours, and Chinese Postman paper.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageUsesEuler Tour
Chinese Postman solutions construct an Eulerian traversal after augmenting the graph.
Often paired withEdmonds' Blossom Algorithm
Undirected Chinese Postman methods are often paired with matching methods for odd-degree vertex pairing.
Related Algorithms
Tags
GraphOptimizationEulerian Path