How do you use a Bidirectional BFS to find the shortest path? Let's say there is a 6x6 grid. The start point is in (0,5) and the end point is in (4,1). What is the shortest path using bidirectional bfs? There are no path costs. And it is undirected.
Asked
Active
Viewed 2.7k times
1 Answers
55
How does Bi-directional BFS work?
Simultaneously run two BFS's from both source and target vertices, terminating once a vertex common to both runs is discovered. This vertex will be halfway between the source and the target.
Why is it better than BFS?
Bi-directional BFS will yield much better results than simple BFS in most cases. Assume the distance between source and target is k, and the branching factor is B (every vertex has on average B edges).
- BFS will traverse
1 + B + B^2 + ... + B^kvertices. - Bi-directional BFS will traverse
2 + 2B^2 + ... + 2B^(k/2)vertices.
For large B and k, the second is obviously much faster the the first.
In your case:
For simplicity I am going to assume that there are no obstacles in the matrix. Here is what happens:
iteration 0 (init):
front1 = { (0,5) }
front2 = { (4,1) }
iteration 1:
front1 = { (0,4), (1,5) }
front2 = { (4,0), (4,2), (3,1), (5,1) }
iteration 2:
front1 = { (0,3), (1,4), (2,5) }
front2 = { (3,0), (5,0), (4,3), (5,2), (3,2), (2,1) }
iteration 3:
front1 = { (0,2), (1,3), (2,4), (3,5) }
front2 = { (2,0), (4,4), (3,3), (5,3), (2,2), (1,1), }
iteration 4:
front1 = { (0,1), (1,2), .... }
front2 = { (1,2) , .... }
Now, we have discovered that the fronts intersect at (1,2), together with the paths taken to get there from the source and target vertices:
path1: (0,5) -> (0,4) -> (0,3) -> (0,2) -> (1,2)
path2: (4,1) -> (3,1) -> (2,1) -> (1,1) -> (1,2)
We now just need to reverse path 2 and append it to path 1 (removing one of the common intersecting vertices of course), to give us our complete path:
(0,5) -> (0,4) -> (0,3) -> (0,2) -> (1,2) -> (1,1) -> (2,1) -> (3,1) -> (4,1)
Mike Chamberlain
- 39,692
- 27
- 110
- 158
amit
- 175,853
- 27
- 231
- 333
-
1Nice explanation. Wondering how would you store all the paths in order to trace back when there is a intersection between the queues? It would take a lot of space for each nodes if we store all the paths. – newbie_old Sep 05 '16 at 21:05
-
@newbie_old [Similar to regular BFS](http://stackoverflow.com/q/9590299/572670), each node you discover, you mark up how you discover it. (In bidirectional BFS special care for the intersecting node which should have two parents). Then, you go back from the node up until the root. The space requirement is linear in the number of vertices, which is the required space for BFS anyway (for the `visited` set and for the queue). – amit Sep 05 '16 at 21:13
-
So time complexity is reduced by square-root; while space complexity is the same? – LookIntoEast Jan 22 '18 at 08:01
-
@user815408 In asymptotic notations, yes. (For example, the required space is doubled, but this is in the same asymptotic complexity). – amit Jan 22 '18 at 12:40
-
@amit I wonder why its time is better than the usual BFS? we have to check the whole "visited" array for having an intersection after every dequeue operation (i.e for each new level) and since we process d/2 levels in bidirectional BFS, we are going to do V×(d/2) comparisons in total and V here is at least as much as b^d. What's the point then? Can somebody explain me where I might be wrong? – mangusta Mar 03 '19 at 13:39
-
@mangusta I am not sure I am following your question. You don't need to check each "discivered" node against all others, you use tree/hash based DS to do it, and it's linear/quasilinear time – amit Mar 03 '19 at 20:52
-
@amit right, I figured out that we don't need to check all nodes everytime we discover a new level. The code that I was analyzing on a particular website (will not mention its name here) was misleading. Whenever we discover a node on traversal A, we simply need to check its discovery status in `discovered` array of traversal B and vice versa – mangusta Mar 04 '19 at 00:57