Published by Dimitris Kougioumtzis · Updated
Store the cheapest path for each visited subset and final vertex, then close the tour back to vertex 0. Reconstruct an exact minimum directed tour.
A state records the visited vertex subset and the final vertex of a path starting at zero. Extend the path to an unvisited vertex, save its predecessor, and close a full-subset path back to zero.
When to use Held-Karp traveling salesperson
Exact small-instance directed traveling-salesperson problems and demonstrations of subset dynamic programming.
Choosing an alternative
Enumerating every tour costs factorial time; Held-Karp reuses subset states in O(n^2 * 2^n) time. Hamiltonian-cycle backtracking checks feasibility without minimizing weights.
Worked example: input and state changes
Example input
0,10,15,20;5,0,9,10;6,13,0,12;8,8,9,0
These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.
Step 0: Rows are visited bitmasks; columns are final vertices. Start with only vertex 0 visited.
State at this checkpoint
{ "values": [ "infinity", "infinity", "infinity", "infinity", 0, "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity" ], "active": [], "kind": "matrix", "columns": 4 }Step 4: Subset 11: extend 1 > 2, cost 19.
State at this checkpoint
{ "values": [ "infinity", "infinity", "infinity", "infinity", 0, "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", 10, "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", 15, "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", 19, "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", 20, "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity" ], "active": [ 30 ], "kind": "matrix", "columns": 4 }Step 8: Subset 111: extend 1 > 3, cost 38.
State at this checkpoint
{ "values": [ "infinity", "infinity", "infinity", "infinity", 0, "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", 10, "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", 15, "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", 28, 19, "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", 20, "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", 20, "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", 27, "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", 38 ], "active": [ 63 ], "kind": "matrix", "columns": 4 }Step 12: Subset 1011: extend 1 > 2, cost 37.
State at this checkpoint
{ "values": [ "infinity", "infinity", "infinity", "infinity", 0, "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", 10, "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", 15, "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", 28, 19, "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", 20, "infinity", "infinity", "infinity", "infinity", "infinity", 28, "infinity", 20, "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", 29, 27, "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", 37, 31 ], "active": [ 62 ], "kind": "matrix", "columns": 4 }Step 16: Minimum tour cost = 35: 0 > 1 > 3 > 2 > 0.
State at this checkpoint
{ "values": [ "infinity", "infinity", "infinity", "infinity", 0, "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", 10, "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", 15, "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", 28, 19, "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", 20, "infinity", "infinity", "infinity", "infinity", "infinity", 28, "infinity", 20, "infinity", "infinity", "infinity", "infinity", "infinity", "infinity", 29, 27, "infinity", "infinity", "infinity", "infinity", "infinity", 35, 29, 31 ], "active": [], "kind": "matrix", "columns": 4, "result": 35, "path": [ 0, 1, 3, 2, 0 ] }
Expected final state
Minimum tour cost = 35: 0 > 1 > 3 > 2 > 0.
Complexity and input bounds
Family: Dynamic programming. Time complexity: O(n^2 * 2^n).
Implementation detail: The matrix has one row per visited bitmask and one column per final vertex. Inputs are bounded to five vertices so all nine downloads fit the portable scratch-buffer contract. Downloads return -1 when no tour exists; success writes n+1 vertices including the repeated start. A single vertex returns cost zero and [0,0].
Space complexity: O(n * 2^n) auxiliary storage for costs and predecessor states, excluding saved visualization frames.
Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.
Square cost matrix, 1..5 vertices; rows separated by semicolons. Diagonal 0; off-diagonal -1 means absent, 0..99 are valid costs.
The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.
Common mistakes and limitations
Missing edges use -1; zero is a valid edge cost. A cheapest Hamiltonian path may lack a closing edge. Keep predecessor state indexed by both subset and final vertex. Equal-cost tours need not be unique.
Further reading
For background on algorithm analysis and the JavaScript function interface:
- MIT OpenCourseWare: algorithm design and analysis foundations
- MDN: JavaScript function parameters and return values
Editorial and testing approach · Browse all algorithm guides
Complete JavaScript implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | // Directed n by n row-major costs, n 1..5. Diagonal 0; off-diagonal -1 means absent, 0..99 are valid costs. Returns exact minimum tour cost starting/ending at 0, or -1 if no tour exists. On success writes n+1 vertices to output (capacity at least n+1); a single vertex returns cost 0 and [0,0]. Ties use the first predecessor/end encountered in ascending DP scan order. O(n^2 * 2^n) time and O(n * 2^n) auxiliary space. Five-vertex bound keeps every scratch array within 256 slots. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation. function algorithm(costs, n, output) { let dist = Array(256).fill(0); let parent = Array(256).fill(0); let states = 1 << n; let next = 0; let candidate = 0; let best = 1000000; let end = -1; let mask = 0; let u = 0; let previous = 0; for (let i = 0; i < states * n; i++) { dist[i] = 1000000; parent[i] = -1; } dist[n] = 0; for (mask = 1; mask < states; mask++) { if ((mask & 1) == 0) { continue; } for (u = 0; u < n; u++) { if (dist[mask * n + u] == 1000000) { continue; } for (let v = 1; v < n; v++) { if ((mask & (1 << v)) == 0 && costs[u * n + v] >= 0) { next = (mask | (1 << v)) * n + v; candidate = dist[mask * n + u] + costs[u * n + v]; if (candidate < dist[next]) { dist[next] = candidate; parent[next] = u; } } } } } if (n == 1) { best = 0; end = 0; } for (let v = 1; v < n; v++) { if (costs[v * n] >= 0 && dist[(states - 1) * n + v] < 1000000) { candidate = dist[(states - 1) * n + v] + costs[v * n]; if (candidate < best) { best = candidate; end = v; } } } if (end < 0) { return -1; } output[n] = 0; mask = states - 1; u = end; for (let i = n - 1; i >= 0; i--) { output[i] = u; previous = parent[mask * n + u]; mask ^= 1 << u; u = previous; } return best; } |
Source
Original primary research on dynamic programming for sequencing problems. The playground demonstrates the bounded bitmask formulation for exact directed traveling-salesperson tours.
- A Dynamic Programming Approach to Sequencing Problems
Michael Held; Richard M. Karp (1962). Research paper.