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

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:

('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'])]

Please provide examples (sample inputs, expected output, actual output) — thefourtheye
– thefourtheye, Commented Oct 1, 2016 at 6:33
Please explain what this output represents. How is this all shortest paths? — A. Sarid
– A. Sarid, Commented Oct 1, 2016 at 8:30
Hello Sarid!Since this is an unweighted graph, the shortest path is the number of levels from the root to the node. In the above example, i am just printing the parents, so it looks confusing. I have been on stack overflow for some time now, but i had never posted questions before(i am learning now), so apologies for the way i have framed the question. — N_B
– N_B, Commented Oct 1, 2016 at 17:03

Saeid · Accepted Answer · 2016-10-01 17:01:18Z

1

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'

edited Oct 1, 2016 at 17:01

answered Oct 1, 2016 at 16:42

Saeid

4,2617 gold badges30 silver badges46 bronze badges

Sign up to request clarification or add additional context in comments.

8 Comments

N_B Over a year ago

Hey!!Thanks for your reply!!I understood what you are trying to do here. While executing the above program, "d.extend(v,level+1)" gives me an error when we reach "level = front[0]". I changed it to "d.append(v,level+1)". It worked for max_depth=2. But it failed for max_depth = 5, so i had to change the condition in while loop to 'len(d)>0'. It works perfectly now. Thank you so much!!!

Saeid Over a year ago

@Nik.Birur I hope you have gotten the idea ;)

N_B Over a year ago

yes!!Thank you so much!!Before you explained, i was so confused, but only after i looked at your solution, i feel it's so easy!!Lol!!Thanks again for the help!!You are the best!!

N_B Over a year ago

Sir, what do you think is the complexity of the above algorithm? I feel its still O(V+E), but however, since we are limiting the depth and also, since we are printing all the shortest paths, does the complexity change??

Saeid Over a year ago

BFS complexity is in O(V+E) even if you think by cutting of from some depth the complexity will decrease it won't become O(V+E)*log(k) because, O(V+E)*log(k) > O(V+E). But the complexity won't decrease. Just imagine a complete a graph. no matter what your max_depth is. You will visit all the nodes.

|

Collectives™ on Stack Overflow

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

1 Answer 1

8 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

8 Comments

Your Answer

Sign up or log in

Post as a guest

Related