title: Solving TSP using dynamic programming in Java
body: <p>I've found many resources online, discussing this and related topics, but I haven't found anything that really helps me know where to start with implementing this solution.</p>
  
  <p>To clarify, starting from city 0, I need to visit every other city once, and return back to city 0.</p>
  
  <p>I have an array such as this one:</p>
  
  <pre><code>   0 1129 1417 1240 1951
  1129    0 1100  800 2237
  1417 1100    0 1890 3046
  1240  800 1890    0 1558
  1951 2237 3046 1558    0
  </code></pre>
  
  <p>Along with finding the optimal route, I need to also find the optimal partial routes along the way. For example, I'd start with routes of length 2, and end up printing out something like this:</p>
  
  <pre><code>S = {0,1}
  C({0,1},1) = 1129
  
  S = {0,2}
  C({0,2},2) = 1417
  
  S = {0,3}
  C({0,3},3) = 1240
  
  S = {0,4}
  C({0,4},4) = 1951
  </code></pre>
  
  <p>Then I'd go to routes of length 3, and print something like this:</p>
  
  <pre><code>S = {0,1,2}
  C({0,1,2},1) = 2517
  C({0,1,2},2) = 2229
  and so on...
  </code></pre>
  
  <p>To make this a dynamic programming solution, I assume I should be saving the shortest distance between any n nodes, and the best way I've thought to do that is with a Hashmap, where the key would be an integer value of every node included in that path, in ascending order (A path going from nodes 0>1>3>4 or 0>1>4>3 could be stored as '134'), and each key would hold a pair that could store the path order as a List, and the total distance as an integer.</p>
  
  <p>At this point I would think I'd want to calculate all paths of distance 2, then all of distance 3, and then take the smallest few and use the hashmap to find the shortest path back for each, and compare.</p>
  
  <p>Does this seem like it could work? Or am I completely on the wrong track?</p>