Nik.Birur - 2 months ago 12

Python Question

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:

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

`[('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)`

`[('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'
```

Source (Stackoverflow)

Comments