algorithm - How do you use a Bidirectional BFS to find the shortest path?

Question

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.

Answer 1

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^k vertices.
• 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)