Travelling Salesman Problem (exact)

Hard

Problem

Given a matrix of distances between n cities, return the length of the shortest tour that starts at city 0, visits every city exactly once, and returns to city 0. n is small (about 15 or fewer), so an exponential bitmask DP is expected.

Example 1

Input:  [[0,10,15,20], [10,0,35,25], [15,35,0,30], [20,25,30,0]]
Output: 80

0 → 1 → 3 → 2 → 0.

Also asked as: Travelling Salesman Problem

Test cases

Case 1

Input:    [[0,10,15,20],[10,0,35,25],[15,35,0,30],[20,25,30,0]]
Expected: 80

Case 2

Input:    [[0,1,2],[1,0,3],[2,3,0]]
Expected: 6

Case 3

Input:    [[0,5],[5,0]]
Expected: 10

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Bitmask DP (Held–Karp)

Time O(2ⁿ · n²)Space O(2ⁿ · n)

dp[mask][i] = shortest path that visits exactly the set `mask` and ends at city i. Extend to an unvisited city j.

function tsp(dist) {
const n = dist.length, FULL = (1 << n) - 1;
const dp = Array.from({ length: 1 << n }, () => new Array(n).fill(Infinity));
dp[1][0] = 0;
for (let mask = 1; mask <= FULL; mask++)
for (let i = 0; i < n; i++) {
if (!(mask & (1 << i)) || dp[mask][i] === Infinity) continue;
for (let j = 0; j < n; j++) {
if (mask & (1 << j)) continue;
const nm = mask | (1 << j);
dp[nm][j] = Math.min(dp[nm][j], dp[mask][i] + dist[i][j]);
}
}
let best = Infinity;
for (let i = 1; i < n; i++) best = Math.min(best, dp[FULL][i] + dist[i][0]);
return best;
}