title: Finding the number of paths of given length in a undirected unweighted graph
body: <p>'Length' of a path is the number of edges in the path.<br/></p>
  
  <p>Given a source and a destination vertex, I want to find the <strong>number of paths</strong> form the source vertex to the destination vertex of <strong>given length</strong> k.</p>
  
  <ul>
  <li><p>We can visit each vertex as many times as we want, so if a path from <code>a</code> to <code>b</code> goes like this: <code>a -&gt; c -&gt; b -&gt; c -&gt; b</code> it is considered valid. This means there can be cycles and we can go through the destination more than once.</p></li>
  <li><p>Two vertices can be connected by more than one edge. So if vertex <code>a</code> an vertex <code>b</code> are connected by two edges, then the paths , <code>a -&gt; b</code> via edge 1 and <code>a -&gt; b</code> via edge 2 are considered different.</p></li>
  <li><p>Number of vertices N is &lt;= 70, and K, the length of the path, is &lt;= 10^9.</p></li>
  <li><p>As the answer can be very large, it is to be reported modulo some number.</p></li>
  </ul>
  
  <p>Here is what I have thought so far:</p>
  
  <p>We can use <a href="http://en.wikipedia.org/wiki/Breadt-first_search" rel="noreferrer">breadth-first-search</a> without marking any vertices as visited, at each iteration, we keep track of the number of edges 'n_e' we required for that path and <strong>product</strong> 'p' of the number of duplicate edges each edge in our path has.</p>
  
  <p>The search search should terminate if the <code>n_e</code> is greater than k, if we ever reach the destination with <code>n_e</code>equal to k, we terminate the search and  add <code>p</code> to out count of number of paths.</p>
  
  <p>I think it we could use a depth-first-search instead of breadth first search, as we do not need the shortest path and the size of Q used in breadth first search might not be enough. </p>
  
  <p>The second algorithm i have am thinking about, is something similar to <a href="http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm" rel="noreferrer">Floyd Warshall's Algorithm</a> using <a href="http://www.iarcs.org.in/inoi/online-study-material/topics/floyd-warshall.php" rel="noreferrer">this</a> approach . Only we dont need a shortest path, so i am not sure this is correct.</p>
  
  <p>The problem I have with my first algorithm is that 'K' can be upto 1000000000 and that means my search will run until it has 10^9 edges and n_e the edge count will be incremented by just 1 at each level, which will be very slow, and I am not sure it will ever terminate for large inputs.</p>
  
  <p>So I need a different approach to solve this problem; any help would be greatly appreciated.</p>