# How bfs could give shortest path

I was solving a problem based on graphs, when I saw its editorial it says the shortest path could be determined by bfs, how??

This is the link to the editorial

can any one explain this??

1 Like

this link is useful for dikstra’s algorithm and show algorithm to dynamic shape

2 Likes

the problem is actually a 0-1 bfs based problem.

Description- In a graph if the weights are either 0 or 1 and we have to find shortest path from one node to another then 0-1 bfs algorithm can be used.

Solution- It is handled by a double ended queue(deque) where we insert the node at front if the edge directed to it has weight 0 and at back if the weight is 1.
This is done because we propagate by always taking out the element from the front of the dequeue as naturally we want to process the node having less distance (just like Dijksta’s algorithm) FIRST.

here’s the code for better understanding-

hope it helps.

1 Like

@thedark

My code is very similar to yours, but there is some mistake its giving wrong answer.Can you please figure it out.

@arpit728

this is the corrected code. You see that when we are using 0-1 bfs the best part is that we need not keep a visited array as the way of insertion in dequeue(front or back) is already doing that job i.e keeping the distance to a particular node to minimal.