solve the traveling salesman problem in javascript in javascript

// Define a helper function to calculate the distance between two nodes
function getDistance(node1, node2) {
  const xDiff = node1.x - node2.x;
  const yDiff = node1.y - node2.y;
  return Math.sqrt(xDiff**2 + yDiff**2);
}

function travelingSalesman(nodes) {
  const n = nodes.length;
  
  // Initialize a 2D array to store the distances between nodes
  const dist = new Array(n).fill(0).map(() => new Array(n).fill(0));
  for (let i = 0; i < n; i++) {
    for (let j = i+1; j < n; j++) {
      const distance = getDistance(nodes[i], nodes[j]);
      dist[i][j] = distance;
      dist[j][i] = distance;
    }
  }
  
  // Initialize DP table with the base case where we start at node 0 and visit no other nodes
  const dp = new Array(1<<n).fill(0).map(() => new Array(n).fill(Infinity));
  for (let i = 0; i < n; i++) {
    dp[1<<i][i] = 0;
  }
  
  // Iterate over all possible subsets of nodes, starting with those with the fewest visited nodes
  for (let s = 0; s < (1<<n); s++) {
    for (let i = 0; i < n; i++) {
      // Skip to the next node in the subset if it's already been visited
      if (!(s & (1<<i))) continue;
      
      // Iterate over all possible subsets of the remaining nodes
      for (let j = 0; j < n; j++) {
        if (i === j || !(s & (1<<j))) continue;
        
        // Update the DP table with the shortest possible distance to visit the remaining nodes
        const prevS = s ^ (1<<i);
        dp[s][i] = Math.min(dp[s][i], dp[prevS][j] + dist[i][j]);
      }
    }
  }
  
  // The optimal tour length is the shortest distance from node 0, visiting all nodes and ending at node 0
  const allNodesVisitedMask = (1<<n)-1;
  let shortestDistance = Infinity;
  for (let i = 0; i < n; i++) {
    shortestDistance = Math.min(shortestDistance, dp[allNodesVisitedMask][i] + dist[i][0]);
  }
  return shortestDistance;
}
1848 chars
52 lines