Branch-and-bound traveling salesperson: Examples & Code

Algorithm Visualizations November 16, 2026 javascript

Published by Dimitris Kougioumtzis · Updated

Explore tours from vertex 0. Bound every partial route by its cost plus minimum outgoing costs for the remaining vertices; prune a bound that cannot improve the incumbent.

Enumerate routes from vertex zero while maintaining the cheapest complete tour found. Add the cheapest outgoing edge for the current end and every unvisited vertex to obtain a lower bound; discard a branch when this bound cannot beat the incumbent.

Open the 3D visualization

Branch-and-bound 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 Branch-and-bound traveling salesperson

Teaching exact branch-and-bound search and admissible pruning on a small directed traveling-salesperson instance.

Choosing an alternative

Held-Karp stores optimal subset states. This view searches route prefixes and prunes with an outgoing-edge lower bound; it remains factorial in the worst case.

Worked example: input and state changes

Example input

0,10,15,20;10,0,35,25;15,35,0,30;20,25,30,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: Start at vertex 0; bounds use one minimum outgoing edge per remaining vertex.

    State at this checkpoint
    {
      "values": [
        1,
        0,
        0,
        0
      ],
      "active": [
        0
      ],
      "kind": "graph",
      "directed": true,
      "chosen": [],
      "visited": [
        0
      ],
      "result": -1,
      "output": [
        -1,
        -1,
        -1,
        -1,
        -1,
        1,
        0
      ],
      "expanded": 1,
      "pruned": 0,
      "lowerBound": 0
    }
  2. Step 7: Extend the partial route; lower bound 70.

    State at this checkpoint
    {
      "values": [
        1,
        2,
        0,
        3
      ],
      "active": [
        3
      ],
      "kind": "graph",
      "directed": true,
      "chosen": [
        0,
        5
      ],
      "visited": [
        0,
        1,
        3
      ],
      "result": -1,
      "output": [
        0,
        1,
        2,
        3,
        0,
        5,
        0
      ],
      "expanded": 5,
      "pruned": 0,
      "lowerBound": 70
    }
  3. Step 14: Prune candidate 1: lower bound 80 cannot beat 80.

    State at this checkpoint
    {
      "values": [
        1,
        0,
        2,
        0
      ],
      "active": [
        2
      ],
      "kind": "graph",
      "directed": true,
      "chosen": [
        1
      ],
      "visited": [
        0,
        2
      ],
      "result": -1,
      "output": [
        0,
        1,
        3,
        2,
        0,
        7,
        1
      ],
      "expanded": 7,
      "pruned": 1,
      "lowerBound": 80
    }
  4. Step 20: Extend the partial route; lower bound 70.

    State at this checkpoint
    {
      "values": [
        1,
        3,
        0,
        2
      ],
      "active": [
        1
      ],
      "kind": "graph",
      "directed": true,
      "chosen": [
        2,
        10
      ],
      "visited": [
        0,
        3,
        1
      ],
      "result": -1,
      "output": [
        0,
        1,
        3,
        2,
        0,
        10,
        2
      ],
      "expanded": 10,
      "pruned": 2,
      "lowerBound": 70
    }
  5. Step 27: Optimal tour cost 80; expanded 11, pruned 4.

    State at this checkpoint
    {
      "values": [
        1,
        2,
        4,
        3
      ],
      "active": [
        0
      ],
      "kind": "graph",
      "directed": true,
      "chosen": [
        0,
        5,
        11,
        6
      ],
      "visited": [
        0
      ],
      "result": 80,
      "output": [
        0,
        1,
        3,
        2,
        0,
        11,
        4
      ],
      "expanded": 11,
      "pruned": 4,
      "lowerBound": 95
    }

Expected final state

Optimal tour cost 80; expanded 11, pruned 4.

Complexity and input bounds

Family: Optimization. Time complexity: O(n! * n) worst case; n <= 7.

Implementation detail: Directed matrices have one through seven vertices, diagonal zero, -1 absent edges and costs 0..99. Downloads return the optimal cost and first lexicographic optimal cycle, plus expanded/pruned counters. Exhaustive permutation fixtures verify routes; a hand-checked case verifies that pruning actually occurs.

Space complexity: O(n) route, minimum-edge and traversal state excluding the n by n input matrix and saved 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 1..7 directed cost matrix, diagonal 0, -1 absent, other costs 0..99. Returns a cycle from vertex 0.

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

A lower bound may underestimate the completion but must never overestimate it. Include the return edge to zero. Missing edges and no-tour outcomes must not be confused with zero-cost edges.

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
// Directed TSP cycle from vertex 0, square n 1..7, diagonal 0, -1 absent, off-diagonal costs 0..99. Returns optimal cost, or -1 if no Hamiltonian cycle. Output capacity n+3: first n+1 entries are the lexicographically first optimal tour including final 0 (all -1 on failure), then expanded partial routes and bound-pruned extensions. Lower bound is spent cost plus the cheapest outgoing cost for the current end and each unvisited vertex. Nonnegative costs; complete bounded search, no heuristic-only success claim. n=1 returns 0 and tour [0,0]. O(n!*n) worst-case time, O(n^2+n) input/traversal storage. 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) {
    if (n < 1 || n > 7) { return -1; }
    for (let i = 0; i <= n; i++) { output[i] = -1; } output[n+1] = 1; output[n+2] = 0;
    if (n == 1) { output[0] = 0; output[1] = 0; return 0; }
    let minOut = Array(256).fill(0); let path = Array(256).fill(0); let used = Array(256).fill(0); let next = Array(256).fill(0); let spent = Array(256).fill(0); let best = 1000000; let depth = 0; let candidate = 0; let edge = 0; let bound = 0; let newCost = 0; let total = 0;
    for (let i = 0; i < n; i++) { minOut[i] = 1000000; for (let j = 0; j < n; j++) { if (i != j && costs[i*n+j] >= 0 && costs[i*n+j] < minOut[i]) { minOut[i] = costs[i*n+j]; } } if (minOut[i] == 1000000) { return -1; } }
    used[0] = 1; next[0] = 1;
    while (depth >= 0) { if (depth == n-1) { edge = costs[path[depth]*n]; if (edge >= 0) { total = spent[depth]+edge; if (total < best) { best = total; for (let i = 0; i < n; i++) { output[i] = path[i]; } output[n] = 0; } } used[path[depth]] = 0; depth--; }
     else { candidate = next[depth]; next[depth]++; if (candidate == n) { used[path[depth]] = 0; depth--; }
     else { edge = costs[path[depth]*n+candidate]; if (used[candidate] == 0 && edge >= 0) { newCost = spent[depth]+edge; bound = newCost+minOut[candidate]; for (let i = 0; i < n; i++) { if (used[i] == 0 && i != candidate) { bound += minOut[i]; } } if (bound >= best) { output[n+2]++; } else { used[candidate] = 1; depth++; path[depth] = candidate; spent[depth] = newCost; next[depth] = 1; output[n+1]++; } } }
     } }
    if (best == 1000000) { return -1; } return best;
}

Source

Foundational branch-and-bound TSP research. The playground uses a simpler admissible minimum-outgoing-edge bound, rather than reproducing the paper reduced-cost-matrix procedure.