×

How bfs could give shortest path

 1 1 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?? asked 20 Jan '16, 17:21 1★arpit728 683●15●62 accept rate: 10%

 2 this link is useful for dikstra's algorithm and show algorithm to dynamic shape answered 20 Jan '16, 23:24 4★frez_95 56●2 accept rate: 50%
 1 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- https://ideone.com/UOIv6U hope it helps. answered 21 Jan '16, 02:05 4★thedark 84●2 accept rate: 9% @thedark My code is very similar to yours, but there is some mistake its giving wrong answer.Can you please figure it out. (22 Jan '16, 07:49) arpit7281★ https://ideone.com/Kvjfff 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 (22 Jan '16, 19:15) thedark4★ @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. (22 Jan '16, 23:36) arpit7281★ @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). (23 Jan '16, 00:00) thedark4★ @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 (23 Jan '16, 01:15) vsp46★ Thank you. (23 Jan '16, 09:00) arpit7281★ showing 5 of 6 show all
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,477
×1,650
×1,197
×487
×125
×27
×12

question asked: 20 Jan '16, 17:21

question was seen: 3,365 times

last updated: 23 Jan '16, 09:00