title: Enumerate all paths in a weighted graph from A to B where path length is between C1 and C2
body: <p>Given two points A and B in a weighted graph, find all paths from A to B where the length of the path is between C1 and C2.</p>
  
  <p>Ideally, each vertex should only be visited once, although this is not a hard requirement. I suppose I could use a heuristic to sort the results of the algorithm to weed out "silly" paths (e.g. a path that just visits the same two nodes over and over again)</p>
  
  <p>I can think of simple brute force algorithms, but are there any more sophisticed algorithms that will make this more efficient? I can imagine as the graph grows this could become expensive.</p>
  
  <p>In the application I am developing, A &amp; B are actually the same point (i.e. the path must return to the start), if that makes any difference.</p>
  
  <p>Note that this is an engineering problem, not a computer science problem, so I can use an algorithm that is fast but not necessarily 100% accurate. i.e. it is ok if it returns <em>most</em> of the possible paths, or if <em>most</em> of the paths returned are within the given length range.</p>
  
  <p>[UPDATE]<br>
  This is what I have so far. I have this working on a small graph (30 nodes with around 100 edges). The time required is &lt; 100ms</p>
  
  <p>I am using a directed graph.<br>
  I do a depth first search of all possible paths.</p>
  
  <ul>
  <li>At each new node<br>
  <ul>
  <li>For each edge leaving the node
  <ul>
  <li>Reject the edge if the path we have already contains this edge (in other words, never go down the same edge in the same direction twice)</li>
  <li>Reject the edge if it leads back to the node we just came from (in other words, never double back. This removes a lot of 'silly' paths)</li>
  <li>Reject the edge if (minimum distance from the end node of the edge to the target node B + the distance travelled so far) > Maximum path length (C2)</li>
  <li>If the end node of the edge is our target node B:
  <ul>
  <li>If the path fits within the length criteria, add it to the list of suitable paths.</li>
  <li>Otherwise reject the edge (in other words, we only ever visit the target node B at the end of the path. It won't be an intermediate point on a path)</li>
  </ul></li>
  <li>Otherwise, add the edge to our path and recurse into it's target node</li>
  </ul></li>
  </ul></li>
  </ul>
  
  <p>I use Dijkstra to precompute the minimum distance of all nodes to the target node.</p>