Introduction

A mail carrier leaves the post office, has to walk down every street in the neighborhood to deliver the mail, and then returns to where they started. The question is simple to state: what is the shortest route that covers every street and ends back home?

This is the Chinese Postman Problem, named after the Chinese mathematician Kwan Mei-Ko, who posed it in 1960. It sounds almost identical to the famous traveling salesman, who must visit every city — and that one is notoriously, provably hard.

But there is a twist. The postman cares about streets (the edges of the map), not cities (the points). And that single change flips the problem from one of the hardest we know to one we can solve quickly and exactly, every time.

Try It: Cover Every Street

Here is a small street map. The postman must traverse every street at least once and finish back at the start. If you could walk each street exactly once you'd be done with no wasted steps — but that is only possible when every junction has an even number of streets meeting at it.

<p class="hint">A small street map. The postman must walk <b>every</b> street and return to the start. Press <b>Solve optimally</b> to see the trick: streets that must be repeated are drawn thick and red. Checking a route is easy — finding the shortest covering route is solvable fast and exactly.</p>
<svg id="map" viewBox="0 0 320 230" aria-label="street map"></svg>
<div class="status" id="status">Press "Solve optimally".</div>
<div class="btns">
  <button id="solve" type="button">Solve optimally</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; }
#map { width: 100%; max-width: 360px; height: auto; display: block; margin: 0 auto; }
.edge { stroke: #9aa3ad; stroke-width: 4; stroke-linecap: round; }
.edge.dup { stroke: #e63946; stroke-width: 8; }
.node { fill: #1d3557; }
.node.odd { fill: #f4a261; stroke: #c97b29; stroke-width: 2; }
.nlabel { font: 700 12px ui-monospace, monospace; fill: #fff; text-anchor: middle; dominant-baseline: central; }
.wlabel { font: 600 11px ui-monospace, monospace; fill: #4a5560; text-anchor: middle; }
.status { font-size: 1rem; font-weight: 600; margin: .6rem 0 .4rem; min-height: 1.4em; }
.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.ghost { background: #fff; color: #1d3557; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Chinese Postman Problem: walk every street (edge) and return to start with the least total distance. An Euler tour (each edge once) exists iff every junction has EVEN degree. The only obstacle is the odd-degree junctions — and there is always an even number of them. Pair them up with shortest detours; the cheapest pairing (minimum-weight matching) is the set of streets to repeat. Edmonds & Johnson, 1973: this is solvable in POLYNOMIAL time (unlike NP-hard TSP).

// --- street map: nodes with positions, edges with weights ---
const NODES = {
  A:[40,40], B:[160,30], C:[280,40],
  D:[40,150], E:[160,140], F:[280,150],
  G:[160,210]
};
const EDGES = [
  ['A','B',4],['B','C',4],['A','D',5],['B','E',4],
  ['C','F',5],['D','E',4],['E','F',4],['E','G',3]
];

function degree(){ const d={}; for(const k in NODES)d[k]=0;
  EDGES.forEach(([u,v])=>{ d[u]++; d[v]++; }); return d; }

// all-pairs shortest path (Floyd–Warshall) over the street weights, with next-hop pointers so we can reconstruct the actual detour streets to repeat.
function shortestPaths(){
  const ks=Object.keys(NODES), INF=1e9, dist={}, nxt={};
  ks.forEach(a=>{ dist[a]={}; nxt[a]={}; ks.forEach(b=>{ dist[a][b]= a===b?0:INF; nxt[a][b]=null; }); });
  EDGES.forEach(([u,v,w])=>{ dist[u][v]=w; dist[v][u]=w; nxt[u][v]=v; nxt[v][u]=u; });
  ks.forEach(k=>ks.forEach(i=>ks.forEach(j=>{
    if(dist[i][k]+dist[k][j]<dist[i][j]){ dist[i][j]=dist[i][k]+dist[k][j]; nxt[i][j]=nxt[i][k]; } })));
  return {dist, nxt};
}
function pathEdges(nxt,u,v){ const e=[]; if(nxt[u][v]==null) return e;
  while(u!==v){ const n=nxt[u][v]; e.push([u,n].sort().join('')); u=n; } return e; }

// minimum-weight perfect matching on the odd vertices (brute force: tiny set)
function bestMatching(odd, dist){
  let best={cost:1e9, pairs:[]};
  (function rec(rem, acc, cost){
    if(rem.length===0){ if(cost<best.cost) best={cost, pairs:acc.slice()}; return; }
    const a=rem[0];
    for(let i=1;i<rem.length;i++){ const b=rem[i];
      const rest=rem.filter((_,j)=>j!==0&&j!==i);
      rec(rest, acc.concat([[a,b]]), cost+dist[a][b]);
    }
  })(odd, [], 0);
  return best;
}

function baseCost(){ return EDGES.reduce((s,[,,w])=>s+w,0); }

let solved=false;
function render(){
  const svg=document.getElementById('map'); svg.innerHTML='';
  const deg=degree();
  const odd = Object.keys(deg).filter(k=>deg[k]%2===1);
  let dupSet=new Set(), extra=0;
  if(solved){
    const {dist, nxt}=shortestPaths();
    const m=bestMatching(odd, dist);
    extra=m.cost;
    // mark every street along each matched pair's shortest detour as duplicated
    m.pairs.forEach(([a,b])=>pathEdges(nxt,a,b).forEach(k=>dupSet.add(k)));
  }
  const ns='http://www.w3.org/2000/svg';
  EDGES.forEach(([u,v,w])=>{
    const key=[u,v].sort().join('');
    const [x1,y1]=NODES[u],[x2,y2]=NODES[v];
    const l=document.createElementNS(ns,'line');
    l.setAttribute('x1',x1);l.setAttribute('y1',y1);l.setAttribute('x2',x2);l.setAttribute('y2',y2);
    l.setAttribute('class','edge'+(dupSet.has(key)?' dup':''));
    svg.appendChild(l);
    const t=document.createElementNS(ns,'text');
    t.setAttribute('x',(x1+x2)/2);t.setAttribute('y',(y1+y2)/2-6);
    t.setAttribute('class','wlabel');t.textContent=w; svg.appendChild(t);
  });
  for(const k in NODES){ const [x,y]=NODES[k];
    const c=document.createElementNS(ns,'circle');
    c.setAttribute('cx',x);c.setAttribute('cy',y);c.setAttribute('r',14);
    c.setAttribute('class','node'+(deg[k]%2===1?' odd':''));
    svg.appendChild(c);
    const t=document.createElementNS(ns,'text');
    t.setAttribute('x',x);t.setAttribute('y',y);t.setAttribute('class','nlabel');
    t.textContent=k; svg.appendChild(t);
  }
  return {odd, base:baseCost(), extra};
}

function setStatus(t,cls){ const s=document.getElementById('status'); s.textContent=t; s.className='status '+cls; }

function solve(){
  solved=true; const r=render();
  if(r.odd.length===0){ setStatus(fmt('Every junction is even — one Euler tour covers all%base% with no repeats.', { base: r.base }),'ok'); return; }
  console.log('Odd junctions:', r.odd.join(', '), '| repeated length', r.extra, '| total', r.base+r.extra);
  setStatus(fmt('Odd junctions %odd% are matched. Repeat %extra% of street. Optimal route = %base% + %extra% = %base%%extra%.', { odd: r.odd.join(', '), extra: r.extra, base: r.base }),'ok');
}
document.getElementById('solve').addEventListener('click',solve);
document.getElementById('reset').addEventListener('click',()=>{ solved=false; render(); setStatus('Press "Solve optimally".',''); });
render();
Result
Console

Press Solve optimally and watch the trick. The algorithm finds the junctions with an odd number of streets, pairs them up as cheaply as possible, and marks those connecting paths to be walked twice. Everything else is walked once. The total — every street plus the few unavoidable repeats — is provably the shortest covering route there is.

The Real Complexity

The Chinese Postman looks like it should be intractable, yet it is one of the happy surprises of complexity theory.

  • Status: solved, in polynomial time. In 1973 Jack Edmonds and Ellis Johnson gave an efficient exact algorithm. There is no exponential blow-up and no guessing.
  • The key idea. A route that uses every street exactly once (an Euler tour) exists precisely when every junction has even degree. The only obstacle is the junctions with odd degree — and by a classic theorem there is always an even number of them.
  • Reduce to matching. Pair up the odd junctions and add a shortest detour between each pair; those detours are the streets you must repeat. Choosing the cheapest way to pair them is a minimum-weight matching problem, which Edmonds himself showed can be solved in polynomial time.
  • Contrast with TSP. The traveling salesman must visit every vertex and is NP-hard — no known fast algorithm. Switching "visit every city" to "cover every street" moves the problem from the hardest tier to the easy one.

That is the punchline: two problems that sound like twins sit on opposite sides of the great divide of P vs NP. Covering edges is easy; visiting nodes is hard.

Where It Matters

"Cover every edge of a network with the least travel" — known as arc routing — is everywhere once you look for it:

  • Municipal services: snow plowing, street sweeping, garbage collection and gritting all need every street covered, not every address visited.
  • Utilities and delivery: meter reading, mail rounds and newspaper routes are classic postman tours.
  • Inspection: walking or flying a drone along every power line, pipeline or rail segment to check for faults.
  • Maintenance planning: line painting, leaf removal and patrol routes that must sweep an entire road network.

Because the problem is solved exactly and fast, these routes can be optimized for real city-sized maps. The lesson is broader than logistics: a tiny change in what you must cover — edges instead of nodes — can decide whether a problem joins the easy P vs NP winners or the intractable traveling salesman losers.

Conclusion

The Chinese Postman is a rare gift: a real, useful routing problem that we can solve perfectly and quickly. The whole difficulty collapses into one elegant move — find the odd junctions, match them cheaply, and repeat exactly those streets.

It is also a perfect illustration of how delicate the boundary of difficulty is. Ask the postman to cover every street and the answer is fast and exact; ask the salesman to visit every city and you fall straight into the traveling salesman and the open mystery of P vs NP. Same map, one word changed, opposite worlds.

Share this article

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

Comments

Loading comments...

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