Introduction

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.

Build the Tour

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">Six cities on a map. Christofides builds a tour step by step: a <b>spanning tree</b>, a <b>matching</b> on the odd cities, an <b>Euler walk</b>, then it <b>shortcuts</b> repeats. The result is provably at most 1.5&times; the best possible tour. Step through it and compare with the true optimum.</p>
<div class="wrap">
  <svg id="map" viewBox="0 0 320 240"></svg>
</div>
<div class="status" id="status">Press "Next step" to start.</div>
<div class="btns">
  <button id="step" type="button">Next step</button>
  <button id="optimal" type="button" class="alt">Show optimal tour</button>
  <button id="reset" type="button" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Christofides' 1.5-approximation for METRIC TSP. Steps:
 //  1) minimum spanning tree (MST)
 //  2) the vertices of ODD degree in the MST (there is always an even number)
 //  3) a minimum-weight perfect matching on those odd vertices
 //  4) MST + matching = multigraph where every vertex has EVEN degree -> Euler circuit
 //  5) shortcut repeated visits -> a Hamiltonian tour, length <= 1.5 * optimum.
const P = [ [130,54],[184,120],[58,186],[116,125],[140,198],[219,172] ];
const NAMES = ['A','B','C','D','E','F'];
const n = P.length;
const d = (i,j) => Math.hypot(P[i][0]-P[j][0], P[i][1]-P[j][1]);

// 1) MST via Prim.
function mst(){
  const inT=[0], rest=[1,2,3,4,5], edges=[];
  while(rest.length){
    let best=Infinity,bi=-1,bj=-1,ri=-1;
    inT.forEach(u=>rest.forEach((v,k)=>{ if(d(u,v)<best){best=d(u,v);bi=u;bj=v;ri=k;} }));
    edges.push([bi,bj]); inT.push(bj); rest.splice(ri,1);
  }
  return edges;
}
// degrees from an edge list
function degrees(edges){ const g=Array(n).fill(0); edges.forEach(([a,b])=>{g[a]++;g[b]++;}); return g; }
// 3) min-weight perfect matching on a small odd set (brute force pairings).
function minMatching(odd){
  let best=null,bw=Infinity;
  (function rec(rem,acc,w){
    if(!rem.length){ if(w<bw){bw=w;best=acc.slice();} return; }
    const a=rem[0];
    for(let k=1;k<rem.length;k++){ const b=rem[k];
      const nr=rem.filter((_,i)=>i!==0&&i!==k);
      rec(nr,acc.concat([[a,b]]),w+d(a,b)); }
  })(odd,[],0);
  return best;
}
// 4) Euler circuit (Hierholzer) on the multigraph.
function euler(multi){
  const adj=Array.from({length:n},()=>[]);
  multi.forEach(([a,b],id)=>{ adj[a].push({to:b,id}); adj[b].push({to:a,id}); });
  const used=new Set(), stack=[0], circ=[];
  while(stack.length){ const v=stack[stack.length-1];
    const e=adj[v].find(x=>!used.has(x.id));
    if(e){ used.add(e.id); stack.push(e.to); } else circ.push(stack.pop()); }
  return circ.reverse();
}
// 5) shortcut to a Hamiltonian tour.
function shortcut(circ){ const seen=new Set(),t=[]; circ.forEach(v=>{ if(!seen.has(v)){seen.add(v);t.push(v);} }); t.push(t[0]); return t; }
function tourLen(t){ let s=0; for(let i=0;i<t.length-1;i++) s+=d(t[i],t[i+1]); return s; }
// optimal tour by brute force (5! fixed start).
function optimal(){
  const rest=[1,2,3,4,5]; let best=null,bl=Infinity;
  (function perm(a,r){ if(!r.length){ const t=[0,...a,0],l=tourLen(t); if(l<bl){bl=l;best=t;} return; }
    r.forEach((x,i)=>perm(a.concat(x),r.filter((_,k)=>k!==i))); })([],rest);
  return {tour:best,len:bl};
}

const MST = mst();
const ODD = degrees(MST).map((g,i)=>g%2?i:-1).filter(i=>i>=0);
const MATCH = minMatching(ODD);
const MULTI = MST.concat(MATCH);
const TOUR = shortcut(euler(MULTI));
const OPT = optimal();

const STEPS = [
  {msg:'1) Minimum spanning tree — the cheapest way to connect all cities (no cycles).', draw:s=>{drawEdges(MST,'edge');}},
  {msg:fmt('2) Odd-degree cities (red rings): %map%. Always an even count.', { map: ODD.map(i=>NAMES[i]).join(', ') }), draw:s=>{drawEdges(MST,'edge'); s.odd=true;}},
  {msg:'3) Minimum matching pairs them up cheaply (red dashes).', draw:s=>{drawEdges(MST,'edge'); drawEdges(MATCH,'edge match'); s.odd=true;}},
  {msg:'4) Tree + matching: every city now has even degree, so an Euler circuit exists.', draw:s=>{drawEdges(MULTI,'edge');}},
  {msg:fmt('5) Shortcut repeats -> a tour of %map%. Length %tourLen% (optimum %len%, ratio %v%x).', { map: TOUR.slice(0,-1).map(i=>NAMES[i]).join('-'), tourLen: tourLen(TOUR).toFixed(0), len: OPT.len.toFixed(0), v: (tourLen(TOUR)/OPT.len).toFixed(2) }), draw:s=>{drawTour(TOUR,'edge tour');}, ok:true},
];

const svg='http://www.w3.org/2000/svg';
let phase=-1;
function el(tag,attrs){ const e=document.createElementNS(svg,tag); for(const k in attrs)e.setAttribute(k,attrs[k]); return e; }
function drawEdges(edges,cls){ const m=document.getElementById('map'); edges.forEach(([a,b])=>{
  m.appendChild(el('line',{x1:P[a][0],y1:P[a][1],x2:P[b][0],y2:P[b][1],class:cls})); }); }
function drawTour(t,cls){ const m=document.getElementById('map'); for(let i=0;i<t.length-1;i++){
  m.appendChild(el('line',{x1:P[t[i]][0],y1:P[t[i]][1],x2:P[t[i+1]][0],y2:P[t[i+1]][1],class:cls})); } }
function drawNodes(state){ const m=document.getElementById('map'); P.forEach((p,i)=>{
  const ring=state.odd&&ODD.includes(i);
  m.appendChild(el('circle',{cx:p[0],cy:p[1],r:11,class:ring?'odd':'node'}));
  const tx=el('text',{x:p[0],y:p[1]+4,class:'label'}); tx.textContent=NAMES[i];
  if(ring)tx.setAttribute('fill','#1d3557'); m.appendChild(tx); }); }
function paint(stepDef){ const m=document.getElementById('map'); m.innerHTML=''; const state={odd:false};
  if(stepDef) stepDef.draw(state); drawNodes(state);
  const s=document.getElementById('status'); if(stepDef){ s.textContent=stepDef.msg; s.className='status'+(stepDef.ok?' ok':''); } }

function next(){ phase=Math.min(phase+1,STEPS.length-1); paint(STEPS[phase]); }
function showOpt(){ const m=document.getElementById('map'); m.innerHTML=''; drawTour(OPT.tour,'edge opt'); drawNodes({});
  document.getElementById('status').textContent=fmt('Optimal tour %map%, length %len%. Christofides got %tourLen%.', { map: OPT.tour.slice(0,-1).map(i=>NAMES[i]).join('-'), len: OPT.len.toFixed(0), tourLen: tourLen(TOUR).toFixed(0) });
  document.getElementById('status').className='status ok'; console.log('Christofides',tourLen(TOUR).toFixed(2),'optimal',OPT.len.toFixed(2),'ratio',(tourLen(TOUR)/OPT.len).toFixed(3)); }
function reset(){ phase=-1; paint(null); document.getElementById('status').textContent='Press "Next step" to start.'; document.getElementById('status').className='status'; }

document.getElementById('step').addEventListener('click',next);
document.getElementById('optimal').addEventListener('click',showOpt);
document.getElementById('reset').addEventListener('click',reset);
paint(null);
Result
Console

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.

The Real Complexity

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−3610^{-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.

Where It Matters

"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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/christofides/Content licensed under CC BY-NC 4.0.