Implementing BFS algorithm with a max depth and that prints all shortest paths
<p>This is the BFS algorithm I came up with to print all the shortest paths from root node to any other node in the graph:</p>

<pre><code>d = deque()
d.append(root)
level = 0
while len(d) &gt;= 0 and level &lt;= max_depth:
    u = d.popleft()
    print(adjacency_list[u])
    for v in adjacency_list[u]:
        if visited[v] == 'N':
            if nodes2distances[u] + 1 &lt;= nodes2distances[v]:
                nodes2distances[v] = nodes2distances[u] + 1
                node2parents[v].append(u)
                d.extend(v)
    level += 1
    visited[u] = 'Y'
</code></pre>

<p>The above code works fine when I don't specify the max level condition, however, the output varies every time I run this algorithm with a restriction on level.</p>

<p>1) Could you explain how i could implement this algorithm with level restriction(i.e specifying the maximum level)?</p>

<p>2) Also, could you please let me know if the approach I have taken to solve the problem can be better?</p>

<p>Edit :
Ok!!Sorry, I didn't do it before!! 
Say I have the following edges in a unweighted graph:      </p>

<p><strong>('A', 'B'), ('A', 'C'), ('B', 'C'), ('B', 'D'),('D', 'E'), ('D', 'F'), ('D', 'G'), ('E', 'F'), ('G', 'F')</strong></p>

<p>After implementing my code without the restriction of depth, I get the following output when i call the algorithm for node <strong>'B'</strong>,</p>

<pre><code>[('A', ['B']), ('C', ['B']), ('D', ['B']), ('E', ['D']), ('F', ['D']), ('G', ['D'])]
</code></pre>

<p>However, when I call the same function with a level restriction of 2, i.e., <code>myFunction(graph,'E',2)</code>, I get the following output:</p>

<pre><code>[('A', ['B']), ('C', ['B']), ('D', ['B'])]
</code></pre>

<p>whereas, the expected output is </p>

<pre><code>[('A', ['B']), ('C', ['B']), ('D', ['B']),('E',['D']),('F', ['D']),('G',['D'])]
</code></pre>

<p>You are incrementing level at the wrong place. Each node's level is equal to its parent level plus 1. You should not increment level globally in the <code>while</code> loop. Instead you should store the level of each node you put in the queue. Something like this:</p>

<pre><code>d = deque()
          #node,level
d.append( (root,0   ) )
while len(d) &gt;= 0:
    front = d.popleft()
    u = front[0]
    level = front[1]
    if level &gt;= max_depth:
        break
    print(adjacency_list[u])
    for v in adjacency_list[u]:
        if visited[v] == 'N':
            if nodes2distances[u] + 1 &lt;= nodes2distances[v]:
                nodes2distances[v] = nodes2distances[u] + 1
                node2parents[v].append(u)
                d.append( (v,level+1) )
    visited[u] = 'Y'
</code></pre>

python algorithm shortest-path bfs