Travelling Salesman Problem (exact)
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
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;}