Held-Karp traveling salesperson: Examples & Code

Algorithm Visualizations November 16, 2026 javascript

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.

Open the 3D visualization

Held-Karp traveling salesperson example state preview
Preview of the example's final state. Complete values are available in the worked example and interactive timeline.

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.

  1. 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
    }
  2. 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
    }
  3. 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
    }
  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
    }
  5. 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:

Editorial and testing approach · Browse all algorithm guides

Complete JavaScript implementation

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