Overview
Christofides' algorithm applies to symmetric metric TSP instances: compute a minimum spanning tree, match the tree's odd-degree vertices, take an Euler tour of the resulting even-degree multigraph, then shortcut repeated cities.
CoreSource checked
Christofides Algorithm
Builds a metric TSP tour within 3/2 of optimum using a tree, matching, and shortcutting.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Optimization
- Difficulty
- Intermediate
- Family
- Approximation Algorithms
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 1
- Relationships
- 7
- Code example
- Ready
- Visualization
- Ready
Core Concepts
metric TSPminimum spanning treeperfect matchingEuler tourshortcuttingapproximation guarantee
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n)
Average
O(n log n)
Worst
O(n^2)
Space
O(n)
When to Use
- Use when distances are symmetric and satisfy the triangle inequality.
- Use when a 1.5-approximation guarantee is preferable to an exact exponential method.
When Not to Use
- Avoid when distances are asymmetric, incomplete, or violate the triangle inequality.
- Avoid when exact optimality is required and the instance is small enough for exact search.
What It Does
- Constructs a bounded-approximation tour for symmetric metric TSP.
- Combines an MST with a minimum-weight matching on odd-degree tree vertices.
- Turns the combined multigraph into a Hamiltonian tour by shortcutting an Euler tour.
Use Cases
- Metric route-planning examples where a provable approximation is more important than exact optimality.
- Teaching how MSTs, matchings, Euler tours, and shortcutting combine in approximation algorithms.
- Baseline comparison against TSP heuristics that lack a worst-case guarantee.
Inputs
- Objective, constraints, and candidate variables
- Problem-specific costs or feasibility rules
Outputs
- Best known feasible solution
- Optimality or approximation result when available
Key Formulas (1)
Approximation bound
tourcost ≤ 1.5 · optimalmetric tour
tour_cost <= 1.5 * optimal_metric_tourBounds the returned metric TSP tour relative to the optimum.
Pseudocode
- 1.Verify that the TSP distances are symmetric and metric
- 2.Compute a minimum spanning tree
- 3.Collect the tree vertices with odd degree
- 4.Compute a minimum-weight perfect matching on the odd vertices
- 5.Combine the tree and matching edges into an Eulerian multigraph
- 6.Take an Euler tour and shortcut repeated vertices
- 7.Return the resulting Hamiltonian tour
Canonical Example
- Input
- four cities at the corners of a unit square with Euclidean distances
- Output
- a square tour of cost 4
- Explanation
- A three-edge MST has two odd endpoints; matching those endpoints makes all degrees even, and shortcutting the Euler tour yields the perimeter tour.
Implementation Notes
- Compute an MST, then collect exactly the vertices with odd degree in that tree.
- Run a general matching method on the complete graph induced by the odd vertices.
- Build an Eulerian multigraph from tree and matching edges before shortcutting repeated cities.
Common Pitfalls
- The 3/2 guarantee depends on metric distances and symmetric costs.
- The odd-degree vertices need a minimum-weight perfect matching, not an arbitrary pairing.
- Shortcutting repeated cities is safe only under the triangle inequality.
Interactive Mechanism Walkthrough
Iterative Convergence & State TrajectoryShow combining a spanning tree, odd-degree matching, and shortcutting on a small metric traveling salesperson problem example.
Step 1 of 7: Verify that the TSP distances are symmetric and metric
optimization-mechanismNotes
Christofides' approximation bound is a worst-case guarantee for metric TSP; it is not a claim about nonmetric or asymmetric instances.
Sources (2)
What each reference supports for this entry.
Introduction to Algorithms (CLRS)
BookTextbook support for Christofides Algorithm's algorithm family, complexity framing, and standard implementation concepts.
Open sourceThe Algorithm Design Manual
BookAlgorithm catalog support for Christofides-style metric TSP approximation and its combinatorial optimization context.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Alternatives2-Opt
Optimization · Core
Both address traveling salesperson improvement, but they make different modeling or performance tradeoffs.
Compare with thisAlternativesNearest Neighbor TSP
Optimization · Core
Both address traveling salesperson heuristic, but they make different modeling or performance tradeoffs.
Compare with thisAlternativesLin-Kernighan
Optimization · Specialized
Lin-Kernighan and Christofides Algorithm are practical alternatives within traveling salesperson improvement, with different assumptions and tradeoffs.
Compare with thisUsesEdmonds' Blossom Algorithm
Graph Traversal · Core
A minimum-weight perfect matching on odd-degree vertices can be solved with blossom-style matching methods.
Compare with thisRelationships
View full relationship pageApproximatesHeld-Karp TSP
Christofides gives a polynomial-time metric-TSP approximation where Held-Karp computes an exact exponential solution.
The first construction step is a minimum spanning tree of the metric graph.
A minimum-weight perfect matching on odd-degree vertices can be solved with blossom-style matching methods.
Related Algorithms
Tags
OptimizationMatchingApproximation