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
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
My code is very similar to yours, but there is some mistake its giving wrong answer.Can you please figure it out.
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.
You can read more about it from http://codeforces.com/blog/entry/22276
@thedark
In question there is a constraint that we have to consider self pair also and there could be multiple paths between two nodes. But why we do not need to take any additional care about them.
@arpit728
We are changing the distance of a node iff its distance is decreasing so it is just a fast version of dijkstra’s algorithm and it will pick the path having least cost/distance between two nodes(IF MULTIPLE PATHS EXIST).
@arpit728 self pair is not required. you can easily ignore them. as for multiple paths. it is possible that edges could be like 1->2 and 2->1 in which both are accepted