The site's ninth dynamic programming entry, and the first
whose subproblem is indexed by an exponential state: which subset of waypoints has already
been visited, not a range, a count, or a single position the way every other entry on this page's own
guide is. Hamiltonian Path's own closing paragraph names the
connection directly: it asks whether a cycle visiting every vertex exists at all, while "the famous
Traveling Salesman Problem ... asks for the cheapest Hamiltonian cycle in a
weighted graph, an optimization question." Held–Karp is that optimization question, answered by
dynamic programming instead of the brute-force O(n!) search of every permutation of
waypoints — cutting the cost to O(n² · 2ⁿ), still exponential, but an astronomically
smaller exponential than a factorial.
A patrol route out of Camp, visiting Overlook, Spring, and Ridge exactly once each before returning to Camp. Trail distances between every pair:
Press Step or Run to fill in dp[subset][last] — the
cheapest way to start at Camp, visit every waypoint in subset, and end at
last — one subset/waypoint pair at a time, then watch it close the loop back to Camp and
reconstruct the cheapest full route.
dp[subset][last] — cheapest route from Camp through
exactly subset, ending at last
A brute-force search over permutations repeats itself constantly without realizing it: the
sub-route "start at Camp, visit Overlook then Spring, currently at Spring" costs the same to complete
from here no matter which order Overlook and Spring were visited in to get there. What matters for
the future is only which waypoints are already used up and where the route currently
is — not the order they were visited in. That's the subproblem: dp[mask][j], the
cheapest cost to start at Camp, visit exactly the waypoints in bitmask mask, and end at
waypoint j. The base case is dp[{Camp}][Camp] = 0 — visiting only the start
costs nothing. Every other cell extends a smaller subset by one waypoint:
dp[mask][j] = min over k in mask, k != j, of:
dp[mask without j][k] + dist[k][j]"mask without j" is always a strictly smaller subset than mask
(one fewer bit set), so filling subsets in increasing numeric order guarantees every cell a recurrence
reads from is already finalized. Once every subset is filled, the cheapest full route closes the loop
by trying every waypoint j as the last stop before returning to Camp:
min over j != Camp of dp[full][j] + dist[j][Camp].
Bitmask mask tracks visited waypoints as bits, with Camp's bit (bit 0) fixed on in
every reachable state since every route starts there:
function heldKarp(dist) {
const n = dist.length;
const FULL = 1 << n;
const dp = Array.from({ length: FULL }, () => new Array(n).fill(Infinity));
const parent = Array.from({ length: FULL }, () => new Array(n).fill(-1));
dp[1][0] = 0; // mask = {0} (just the start), ending at 0, costs 0
for (let mask = 1; mask < FULL; mask++) {
if (!(mask & 1)) continue; // every reachable state includes the start
for (let j = 0; j < n; j++) {
if (!(mask & (1 << j)) || dp[mask][j] === Infinity) continue;
for (let k = 0; k < n; k++) {
if (mask & (1 << k)) continue; // k must NOT be visited yet
const nextMask = mask | (1 << k);
const candidate = dp[mask][j] + dist[j][k];
if (candidate < dp[nextMask][k]) {
dp[nextMask][k] = candidate;
parent[nextMask][k] = j;
}
}
}
}
const full = FULL - 1;
let best = Infinity, bestJ = -1;
for (let j = 1; j < n; j++) {
const candidate = dp[full][j] + dist[j][0];
if (candidate < best) { best = candidate; bestJ = j; }
}
// reconstruct the route by walking parent pointers back to the start
const route = [];
let mask = full, j = bestJ;
while (j !== -1) {
route.push(j);
const prevJ = parent[mask][j];
mask ^= (1 << j);
j = prevJ;
}
route.reverse();
return { cost: best, route };
}The inner loop's if (mask & (1 << k)) continue; guard — skip
k if it's already in the subset — isn't an optimization, it's load-bearing.
Drop it, and the recurrence can write into dp[mask][k] where k was already
in mask (so nextMask equals mask itself, not a larger subset),
letting a cheaper-looking "revisit" corrupt an already-finalized cell for a subset the outer loop
hasn't finished processing yet. Stress-tested directly rather than reasoned about in the abstract:
1,000 random distance matrices across sizes 3–7, comparing the guarded version against a
deliberately unguarded one — 135 of 1,000 produced a wrong (too cheap — corresponding
to no real route at all) answer. A concrete instance at n = 4 asymmetric distances:
the guarded version correctly finds a cheapest route costing 14; the unguarded version
reports 12, a cost no actual Hamiltonian cycle on that graph achieves.
Two different-looking routes can legitimately tie when distances are symmetric
(the trail from Overlook to Spring costs the same either direction), because a route and the exact
same route walked backward always cost the same total. A from-scratch brute-force check over all
3! = 6 permutations of Overlook/Spring/Ridge on this page's own demo data confirms the
optimal cost of 19 two ways: Held–Karp's Camp → Ridge → Spring → Overlook →
Camp and brute force's independently-found Camp → Overlook → Spring → Ridge → Camp
are the same cycle in opposite directions, not a discrepancy between the two methods.
Time: O(n² · 2ⁿ) — 2ⁿ subsets, up to n
choices of j per subset, up to n choices of k per j.
Still exponential, but a dramatically smaller exponential than the O(n!) brute force of
trying every permutation directly. Measured directly in this environment (not just asserted): at
n = 12, brute force took ~3.1 seconds against Held–Karp's
~5.8 milliseconds on the same random instance — both agreeing on the optimal cost,
Held–Karp roughly 500× faster already at a size this small, and the gap widens
every time n grows by one. Space: O(n · 2ⁿ) for the table —
which is the real ceiling in practice, not time. Also measured directly: n = 20 (a little
over a million subsets, times 20 waypoints each) finished in ~2.3 seconds but needed roughly
150MB for the table alone in this implementation; the memory bound doubles with every
additional waypoint, so n = 25 would need on the order of 30× that
— multiple gigabytes for the table alone, before accounting for anything else. Held–Karp is the
textbook-optimal exact algorithm for small-to-moderate n (roughly up to the low twenties
on ordinary hardware), not a general answer for large instances — those need approximation or
heuristic methods instead, out of scope for this page.
This site's guide, Choosing a Dynamic Programming Approach, compares this entry against the other ten Dynamic Programming entries side by side.