title: Travelling Sales Man (need to visit only subset of nodes): Bugged
body: <p>I need help with my travelling sales man problem code. Its bugged... I know because its a school assignment and there are test cases. So here it goes. </p>
  
  <p>Given a connected graph where I need to visit a subset of nodes. How do I compute the shortest path? </p>
  
  <p><img src="https://i.stack.imgur.com/SA56G.png" alt="enter image description here"></p>
  
  <p>As an example, refer to above image. I need to start from 0 and visit some/all nodes then go back to zero. In the process, I need to compute the shortest path. </p>
  
  <p>Suppose I need to visit all nodes, I will go from <code>0 -&gt; 1 -&gt; 2 -&gt; 3 -&gt; 0</code> = <code>20 + 30 + 12 + 35 = 97</code>. Suppose now I only need to visit node 2, I will go from <code>0 -&gt; 3 -&gt; 2 -&gt; 3 -&gt; 0</code> as that gives shortest path of 94 (I can visit nodes I don't have to visit if it can give a shortest path). </p>
  
  <p>Basically, I did: </p>
  
  <ol>
  <li><p>Compute shortest path between any 2 pairs of required nodes and the source (0). This gives me a shortest path 2D table like (I used dijkstra's): </p>
  
  <pre><code>  |  0  1  2  3
  --+--------------
  0 | 
  1 |
  2 | 
  3 |
  </code></pre></li>
  <li><p>Now, I modify the shopping sales man algorithm (aka. Floyd Warshall’s or APSP) to use this table. Current Java source (TSP and dijkstra's) looks like: </p>
  
  <pre><code>int TSP(int source, int visited) {
     if (visited == (int)(Math.pow(2, K)-1)) { // all required visited
      return sssp.get(source).get(0); // return to source (0)
    } else if (memo.containsKey(source) &amp;&amp; memo.get(source).containsKey(visited)) {
      return memo.get(source).get(visited);
    } else {
      int item;
      if (!memo.containsKey(source)) {
        memo.put(source, new HashMap&lt;Integer, Integer&gt;());
      }
      memo.get(source).put(visited, 1000000);
      for (int v = 0; v &lt; K; v++) {
        item = shoppingList[v];
        if (!hasVisited(visited, item)) {
          memo.get(source).put(visited, Math.min(
            memo.get(source).get(visited),
            sssp.get(source).get(item) + TSP(item, visit(visited, v))
          ));
        }
      }
      return memo.get(source).get(visited);
    }
  }
  
  int dijkstra(int src, int dest) {
    PriorityQueue&lt;IntegerPair&gt; PQ = new PriorityQueue&lt;IntegerPair&gt;();
    HashMap&lt;Integer, Integer&gt; dist = new HashMap&lt;Integer, Integer&gt;(); // shortest known dist from {src} to {node}
    // init shortest known distance
    for (int i = 0; i &lt; N+1; i++) {
      if (i != src) {
        dist.put(i, Integer.MAX_VALUE); // dist to any {i} is big(unknown) by default
      } else {
        dist.put(src, 0); // dist to {src} is always 0
      }
    }
    IntegerPair node;
    int nodeDist;
    int nodeIndex;
  
    PQ.offer(new IntegerPair(0, src)); 
    while (PQ.size() &gt; 0) {
      node = PQ.poll();
      nodeDist = node.first();
      nodeIndex = node.second();
  
      if (nodeDist == dist.get(nodeIndex)) {
        // process out going edges
        for (int v = 0; v &lt; N+1; v++) { // since its a complete graph, process all edges
          if (v != nodeIndex) { // except curr node
            if (dist.get(v) &gt; dist.get(nodeIndex) + T[nodeIndex][v]) { // relax if possible
              dist.put(v, dist.get(nodeIndex) + T[nodeIndex][v]);
              PQ.offer(new IntegerPair(dist.get(v), v));
            }
          }
        }
      }
    }
    return dist.get(dest);
  }
  </code></pre>
  
  <ol>
  <li><code>visited</code> is used as a bitmask to indicate if a node has been visited</li>
  <li><code>sssp</code> is a <code>HashMap&lt;Integer, HashMap&lt;Integer, Integer&gt;&gt;</code> where the 1st hashmap's key is the source node and the key for 2nd hashmap is the destination. So it basically represent the 2D table u see in point 1. </li>
  <li><code>memo</code> is just what I used in dynamic programming as a "cache" of previously computed shortest path from a node, given a visited bitmap.  </li>
  </ol></li>
  </ol>
  
  <p>Full source: <strong><a href="http://pastie.org/5171509" rel="nofollow noreferrer">http://pastie.org/5171509</a></strong></p>
  
  <p>The test case that passes: </p>
  
  <pre><code>1
  
  3 3
  1 2 3
  0 20 51 35
  20 0 30 34
  51 30 0 12  
  35 34 12 0 
  </code></pre>
  
  <p>Where 1st line is the number of test cases. 3rd line (<code>3 3</code>). The 1st <code>3</code> is the number of nodes, 2nd 3 is the number of required nodes. 4th line is the list of required nodes. Then the rest is the table of edge weights. </p>
  
  <p>The test case that fails is: </p>
  
  <pre><code>9 9
  1 2 3 4 5 6 7 8 9
  0 42 360 335 188 170 725 479 359 206
  42 0 402 377 146 212 767 521 401 248
  360 402 0 573 548 190 392 488 490 154
  335 377 573 0 293 383 422 717 683 419
  188 146 548 293 0 358 715 667 539 394
  170 212 190 383 358 0 582 370 300 36
  725 767 392 422 715 582 0 880 704 546
  479 521 488 717 667 370 880 0 323 334
  359 401 490 683 539 300 704 323 0 336
  206 248 154 419 394 36 546 334 336 0
  </code></pre>
  
  <p>I got 3995 but the answer is 2537... sorry I know this is hard to debug ... I am having the same problem, the test case is too large ... at least for humans ... so I am creating smaller test case to test but they seem to pass ... </p>