Nik.Birur 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()
print(adjacency_list[u])
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'])]

Answer

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
    print(adjacency_list[u])
    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.append( (v,level+1) )
    visited[u] = 'Y'
Comments