You are not logged in. Please login at www.codechef.com to post your questions!

×

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

arpit728's gravatar image

1★arpit728
6831562
accept rate: 10%


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

link

answered 20 Jan '16, 23:24

frez_95's gravatar image

4★frez_95
562
accept rate: 50%

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.

link

answered 21 Jan '16, 02:05

thedark's gravatar image

4★thedark
842
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★

@arpit728

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★

@thedark and @vsp4

Thank you.

(23 Jan '16, 09:00) arpit7281★
showing 5 of 6 show all
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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