Travelling Salesman Problem using Dynamic Programming Hard 0 attempts
GeeksforGeeks ↗

Travelling Salesman Problem using Dynamic Programming

Hard GraphBFSDFS GeeksforGeeks

You're given a matrix of pairwise distances between a set of cities. Starting from any city, find a route that visits every other city exactly once and returns to the starting point, minimizing the total distance traveled.

Input Format
Implement tsp(dist). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

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

Example 2

Input
dist = [[0,5],[5,0]]
Output
10
Constraints
  • 1 <= dist.length <= 20
  • dist is square with diagonal entries 0.
  • Off-diagonal distances are integers in [1,10^4].
Test Cases (2)
Case 1
Args: [[[0,10,15,20],[10,0,35,25],[15,35,0,30],[20,25,30,0]]] Expected: 80
Case 2
Args: [[[0,5],[5,0]]] Expected: 10
Topics
GraphBFSDFS

Bitmask DP (Held-Karp)

javascript
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