Christofides Algorithm

A delivery van has to visit a dozen stops and come home. What's the shortest route? This is the travelling salesman problem (TSP), and finding the exact shortest tour is NP-hard — for a real city map, the number of possible routes explodes faster than any computer can check.

So we change the question. Instead of "what is the best route?", we ask: "can we quickly find a route that is guaranteed to be close to the best?" In 1976 Nicos Christofides answered with a beautiful yes — for the common case where distances obey the triangle inequality (going direct is never longer than a detour), his algorithm always returns a tour at most 1.5 times the optimum.

The trick is to never search through routes at all. Instead it stitches a tour together out of two classic ingredients — a spanning tree and a matching — each of which we can compute quickly. That combination is one of the most elegant results in all of algorithm design.

Here are six cities. The optimum tour is hidden — but Christofides never looks for it. Press Next step to watch it assemble a route out of simpler pieces, then press Show optimal tour to compare.

<p class="hint">{{hint}}</p>
<div class="wrap">
  <svg id="map" viewBox="0 0 320 240"></svg>
</div>
<div class="status" id="status">{{status_initial}}</div>
<div class="btns">
  <button id="step" type="button">{{btn_step}}</button>
  <button id="optimal" type="button" class="alt">{{btn_optimal}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
.wrap { background: #f4f7fa; border: 1px solid #cdd9e3; border-radius: 10px; padding: 6px; }
svg { width: 100%; height: auto; display: block; }
.edge { stroke: #1d3557; stroke-width: 2.4; fill: none; }
.edge.match { stroke: #e63946; stroke-width: 2.8; stroke-dasharray: 6 4; }
.edge.tour { stroke: #2a9d8f; stroke-width: 3.4; }
.edge.opt  { stroke: #e9a200; stroke-width: 3.4; }
.node { fill: #1d3557; }
.label { fill: #fff; font: 700 11px system-ui, sans-serif; text-anchor: middle; }
.odd { stroke: #e63946; stroke-width: 3; fill: #fff; }
.odd + .label { fill: #1d3557; }
.status { font-size: .98rem; font-weight: 600; margin: .55rem 0; min-height: 1.4em; color: #1d3557; }
.status.ok { color: #0a7d33; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.alt { background: #e9a200; border-color: #c98900; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Each step is something we can compute fast. (1) A minimum spanning tree links every city as cheaply as possible. (2) Some cities end up with an odd number of tree edges; there is always an even number of these odd cities. (3) A minimum-weight matching pairs them up. (4) Tree + matching gives every city an even degree, so an Euler circuit — a walk using every edge once — exists. (5) Walking it while skipping cities you've already seen gives a real tour. The two halves are exactly why the result can't exceed 1.5× the best: the tree costs at most the optimum, and the matching at most half of it.

What exactly does Christofides buy us?

• The problem is NP-hard. Computing the exact shortest tour is intractable; general TSP can't even be approximated within any constant factor unless P = NP.
• The metric case is gentler. When distances satisfy the triangle inequality, good approximation becomes possible — and Christofides is the classic result.
• The algorithm is polynomial. Every ingredient is efficient: a minimum spanning tree, a minimum-weight perfect matching (the slowest piece, roughly cubic), and an Euler-circuit walk. No exponential search anywhere.
• The guarantee is proven, not hoped for. Tree cost ≤ optimum, and the matching on the odd vertices costs ≤ half the optimum, so the assembled tour is ≤ 1.5 × optimum — always, on every input.
• It held the record for 44 years. From 1976 until 2020, nobody could beat 1.5× for metric TSP. Then Karlin, Klein and Oveis Gharan shaved it by a microscopic amount (about $10^{-36}$), confirming the question is still wide open.

So Christofides doesn't make TSP easy — it makes a promise about how wrong you can be. That is the whole spirit of approximation: when P vs NP blocks the perfect answer, demand a guaranteed-good one instead.

"Get close to optimal, fast, with a promise attached" is exactly what real operations need:

• Logistics and delivery: planning routes for trucks, mail carriers and field technicians, where a provably-near-optimal route saves real fuel and time.
• Manufacturing: a drill that punches thousands of holes in a circuit board, or a laser cutting a sheet, is solving a TSP — shorter travel means faster output.
• Genomics and astronomy: ordering DNA fragments or pointing a telescope between targets are routing problems in disguise.
• A blueprint for other problems: the "build a structure, then repair it" pattern in Christofides inspired approximation algorithms far beyond routing, including vertex cover and facility location.

Understand Christofides and you've grasped the core idea of approximation algorithms — the practical answer to problems that, like P vs NP, refuse to be solved exactly.

Christofides' algorithm is a small miracle of restraint: it never searches for the perfect route, yet it can prove its answer is at most 50% too long. By gluing together a spanning tree and a matching — two things we know how to compute — it sidesteps the intractability of the travelling salesman problem entirely.

For nearly half a century its 1.5× guarantee was simply the best anyone could do, and even the 2020 improvement barely moved the needle. That endurance is the lesson: when a problem is provably hard, the smart move isn't a faster brute force — it's a clever construction with a promise you can trust. Christofides remains the textbook example of taming the impossible.