Algorithm/Approach to find destination node from source node of exactly k edges in undirected graph of billion nodes without cycle
<p>Consider I have an adjacency list of billion of nodes structured using hash table arranged in the following manner:</p>

<p>key = source node <br/>
value = hash_table { node1,  node2, node3}</p>

<p>The input values are from text file in the form of <br/>
<strong>from</strong>,<strong>to</strong><br/>
1,2<br/>
1,5<br/>
1,11<br/>
... so on</p>

<p><strong>eg.
key = '1' <br/>
value = {'2','5','11'} <br/>
means 1 is connected to nodes 2,5,11</strong></p>

<p>I want to know an algorithm or approach to find destination node from source node of exactly k edges in an undirected graph of billion nodes without cycle </p>

<p><strong>for eg. from node 1 I want to find node 50 only till depth 3 or till 3 edges.</strong></p>

<p>My assumption the algorithm finds 1 - 2 - 60 - 50 which is the shortest path but how would the traversing be efficient using the above adjacency list structure?
I do not want to use Hadoop/Map Reduce. </p>

<p>I came up with naive solution as below in Python but is not efficient. Only thing is hash table searches key in O(1) so I could just search neighbours and their billion neighbours directly for the key. The following algo takes lot of time.</p>

<ol>
<li>start with source node</li>
<li>use hash table search for finding key</li>
<li>go 1 level deeper with hash table of neighbor nodes and find their values for destination nodes until node found</li>
<li>Stop if node not found on k depth</li>
</ol>


&nbsp1 <br/>
&nbsp&nbsp| <br/>
{2 &nbsp &nbsp&nbsp&nbsp  &nbsp      5  &nbsp&nbsp&nbsp&nbsp&nbsp  &nbsp&nbsp&nbsp      11} <br/>
&nbsp&nbsp | &nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp         |  &nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp         | <br/>
{3,6,7}  {nodes}     {nodes} .... connected nodes <br/>
&nbsp |&nbsp | &nbsp| &nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp     |     &nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp      | <br/>
{nodes}   {nodes}    {nodes} .... million more connected nodes. <br/>


<p><br/>Please suggest. The algorithm above implemented similar to BFS takes more than 3 hours to search for all the possible key value relationships. Can be it be reduced with other searching method? </p>