title: Implementing nearest neighbour algorithm in Java (using dynamic programming)
body: <p>I am trying to implement a method that executes the nearest neighbour algorithm in Java. I want to find the shortest path by executing the algorithm from each possible starting city in a table. The method is passed a <code>table[i][j] == table[j][i]</code> of the cost of travel between city <code>i</code> and <code>j</code>.</p>
  <p>I have searched using Google, but I still do not understand how one implements such an algorithm when given a table of this sort. And this is my first time working with such an algorithm, so I have no experience with it. I think it involves dynamic programming (specifically, &quot;table lookup&quot;), resulting in a time complexity of O(n^3). In particular, I think it is the dynamic programming aspect of this that I am having difficulty conceptualizing.</p>
  <h2>Edit</h2>
  <p><a href="https://www1.cs.columbia.edu/CAVE/publications/pdfs/Kumar_ECCV08_2.pdf" rel="nofollow noreferrer">This</a> seems like it mentions it:</p>
  <blockquote>
  <p>We use several techniques to significantly improve the efficiencies of
  the different NN algorithms (in some cases exploiting the inherent
  properties of images). These include precomputing or using look-up
  tables for computing distances, ...</p>
  </blockquote>
  <p>And see section 4.1.</p>