title: How to modify this Held-Karp algorithm to search for Hamiltonian path instead of cycle?
body: <p>I implemented Held-Karp in Java following <a href="https://en.wikipedia.org/wiki/Held%E2%80%93Karp_algorithm" rel="nofollow noreferrer">Wikipedia</a> and it gives the correct solution for total distance of a cycle, however I need it to give me the path (it doesn't end on the same vertex where is started). I can get path if I take out the edge with largest weight from the cycle, but there is a possibility that 2 different cycles have same total distance, but different maximum weight, therefore one of the cycles is wrong.</p>
  
  <p>Here is my implementation:</p>
  
  <pre><code>//recursion is called with tspSet = [0, {set of all other vertices}]
  
  private static TSPSet recursion (TSPSet tspSet) {
      int end = tspSet.endVertex;
      HashSet&lt;Integer&gt; set = tspSet.verticesBefore;
  
      if (set.isEmpty()) {
          TSPSet ret = new TSPSet(end, new HashSet&lt;&gt;());
          ret.secondVertex = -1;
          ret.totalDistance = matrix[end][0];
          return ret;
      }
  
      int min = Integer.MAX_VALUE;
      int minVertex = -1;
      HashSet&lt;Integer&gt; copy;
  
      for (int current: set) {
          copy = new HashSet&lt;&gt;(set);
          copy.remove(current);
  
          TSPSet candidate = new TSPSet(current, copy);
  
          int distance = matrix[end][current] + recursion(candidate).totalDistance;
  
          if (distance &lt; min) {
              min = distance;
              minVertex = current;
          }
      }
  
      tspSet.secondVertex = minVertex;
      tspSet.totalDistance = min;
  
      return tspSet;
  }
  
  class TSPSet {
      int endVertex;
      int secondVertex;
      int totalDistance;
      HashSet&lt;Integer&gt; verticesBefore;
  
      public TSPSet(int endVertex, HashSet&lt;Integer&gt; vertices) {
          this.endVertex = endVertex;
          this.secondVertex = -1;
          this.verticesBefore = vertices;
      }
  }
  </code></pre>