Travelling Salesman Problem using Dynamic Programming Hard 0 attempts
GeeksforGeeks ↗

Travelling Salesman Problem using Dynamic Programming

Hard GraphBFSDFS GeeksforGeeks

Given a matrix of distances between cities, find the shortest possible route visiting all cities exactly once and returning to the origin.

Example: dist = [[0,10,15,20],[10,0,35,25],[15,35,0,30],[20,25,30,0]] → Output: 80

Sample Input
—
Sample Output
—
Constraints
  • 1 <= N <= 20
  • 1 <= cost[i][j] <= 10^4
Topics
GraphBFSDFS

Bitmask DP (Held-Karp)

function tsp(dist) {
  const n = dist.length, ALL = (1<<n)-1;
  const dp = Array.from({length:1<<n}, ()=>Array(n).fill(Infinity));
  dp[1][0] = 0;
  for (let mask=1;mask<=ALL;mask++) {
    for (let u=0;u<n;u++) {
      if (!(mask&(1<<u)) || dp[mask][u]===Infinity) continue;
      for (let v=0;v<n;v++) {
        if (mask&(1<<v)) continue;
        const next = mask|(1<<v);
        dp[next][v] = Math.min(dp[next][v], dp[mask][u]+dist[u][v]);
      }
    }
  }
  let min = Infinity;
  for (let u=0;u<n;u++) min = Math.min(min, dp[ALL][u]+dist[u][0]);
  return min;
}

Time: O(2^n × n²) | Space: O(2^n × n)

Saved in this browser only. Private to you.

JavaScript