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.

Eyesore

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)

Bughouse

Nice 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. – Internship

@Internship Similar to regular BFS, 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). – Bughouse

So time complexity is reduced by square-root; while space complexity is the same? – Staff

@user815408 In asymptotic notations, yes. (For example, the required space is doubled, but this is in the same asymptotic complexity). – Bughouse

@Bughouse 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? – Burge

@Burge 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 – Bughouse

@Bughouse 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 – Burge