Nik.Birur - 2 months ago 12
Python Question

Implementing BFS algorithm with a max depth and that prints all shortest paths

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:

``````d = deque()
d.append(root)
level = 0
while len(d) >= 0 and level <= max_depth:
u = d.popleft()
for v in adjacency_list[u]:
if visited[v] == 'N':
if nodes2distances[u] + 1 <= nodes2distances[v]:
nodes2distances[v] = nodes2distances[u] + 1
node2parents[v].append(u)
d.extend(v)
level += 1
visited[u] = 'Y'
``````

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.

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

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

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

('A', 'B'), ('A', 'C'), ('B', 'C'), ('B', 'D'),('D', 'E'), ('D', 'F'), ('D', 'G'), ('E', 'F'), ('G', 'F')

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

``````[('A', ['B']), ('C', ['B']), ('D', ['B']), ('E', ['D']), ('F', ['D']), ('G', ['D'])]
``````

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

``````[('A', ['B']), ('C', ['B']), ('D', ['B'])]
``````

whereas, the expected output is

``````[('A', ['B']), ('C', ['B']), ('D', ['B']),('E',['D']),('F', ['D']),('G',['D'])]
``````

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 `while` loop. Instead you should store the level of each node you put in the queue. Something like this:

``````d = deque()
#node,level
d.append( (root,0   ) )
while len(d) >= 0:
front = d.popleft()
u = front[0]
level = front[1]
if level >= max_depth:
break