Menu
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.
527
To find the shortest path, all you have to do is start from the source and perform a breadth first search and stop when you find your destination Node. The only additional thing you need to do is have an array previous[n] which will store the previous node for every node visited. The previous of source can be null.
Heuristic refers to the concept of finding the shortest path from the current node in the graph to the goal node. The search always takes the shortest path to the goal node.
Bidirectional search replaces one single search graph with two small subgraphs in which one starts the search from an initial vertex and other starts from goal vertex. The search stops when these two graphs intersect each other. Bidirectional search can use search techniques such as BFS, DFS, DLS, etc.
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).
1 + B + B^2 + ... + B^k vertices.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)
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
