title: Feedback on algorithm for Steiner Tree with restrictions
body: <p>For an assignment, I have to create a <a href="http://en.wikipedia.org/wiki/Steiner_tree_problem" rel="nofollow">Steiner Tree</a>.  However, this is not a typical Steiner Tree, as the graph structure we're required to use does not allow insertion of new vertices.  Rather, the test cases define a graph structure of N vertices and M edges while specifically marking X vertices as target nodes.  These are the nodes we have to span while using some, none or all of the unmarked vertices in the graph.</p>
  
  <p>My solution to this problem is</p>
  
  <ol>
  <li>Implement <a href="http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm" rel="nofollow">Dijkstra's Algorithm</a> to find the shortest path between all the target vertices</li>
  <li>For each of the shortest paths 1:n
  <ol>
  <li>Extract all current selected path vertices into a set</li>
  <li>Extract all remaining vertices into a set</li>
  <li>For all vertices of the current selected path 1:m
  <ol>
  <li>Execute Dijkstra to find shortest path between current vertex and other path's vertices</li>
  <li>If this creates a spanning tree, save path and length in priority queue sorted by length value</li>
  </ol></li>
  </ol></li>
  <li>Pop top of priority queue and return path</li>
  </ol>
  
  <p>My issue is that this is an exhaustive search that uses the initial application of Dijkstra to create a reduced set of possible start-end vertices for a shorter path than a minimum spanning tree.  </p>
  
  <p>Is there a heuristic or other algorithm that may solve this problem?</p>