title: Python TSP Held-Karp algorithm
body: <p>I'm trying to implement Held-Karp in Python but it doesn't seem to be working. There are two differences in my problem from the classical TSP problem (as used in the description of the H-K algorithm I found in the web):
  - I don't need to return to the original node. I think this is called a Hamiltonian cycle but I'm not very familiar with graph algorithms so I'm not entirely sure. Each city needs to be visited once as in TSP
  - Some edges in the graph are missing</p>
  
  <p>I used networkx and created this function:</p>
  
  <pre><code>def hk(nodes,Graph,start_node, total_ops, min_weight = 9999999,min_result = []):
  nodes.remove(start_node)
  # removes the current node from the set of nodes
  for next_node in nodes:
  
      total_ops += 1
      current_weight = 0
      try:
          current_weight += Graph[start_node][next_node]["weight"]
          # checks if there's an edge between the current node and the next node
  # If there's an edge, adds the edge weight
      except:
          continue
      sub_result = []
      if len(nodes) &gt; 1:
          new_nodes = set(nodes)
          sub_result,sub_weight,total_ops = hk(new_nodes,Graph,next_node, total_ops) 
  #calculates the minimum weight of the remaining tree
          current_weight += sub_weight
      if current_weight &lt; min_weight:
  # if the weight of the tree is below the minimum weight, update minimum weight
          min_weight = current_weight
          min_result = [next_node] + sub_result
  return min_result,min_weight,total_ops
  </code></pre>
  
  <p>But something is clearly wrong as I'm expecting O(n ** 2 * 2 ** n) complexity but am getting O(n!) instead, same as for the brute force method (trying all combinations one by one). Clearly, there's an error in my implementation.</p>
  
  <p>Thank you.</p>