Everyone gets bidirectional BFS wrong
zdimension.frI saw this via Lobsters yesterday and enjoyed reading it. The animations helped me understand bidiBFS.
But I'm confused by the example showing the buggy version of the algorithm fail. This is in the section "Finding the Wrong Path".
Consider the state of the algorithm after the first step. We've explored S and added its neighbors to the queue, Q = [T, a1, b1].
In the next step we explore T, the first node in the queue. We add its neighbors , a3 and b2, to the queue.
Now, I would expect the new value of Q to be something like [a1, b1, a3, b2] (depending on the order we add T's neighbors). In this case we would process a1, and b1 next, notice that b1 is adjacent to b2, and correctly find the shortest path S-b1-b2-T.
But the animation actually shows that after step 2, Q = [a1, a3, b1, b3]. In other words, a3 didn't join the back of the queue but jumped in front of b1. This is what leads to the buggy behavior that is shown.
So as I understand the example, this would have worked fine if Q were actually a queue. But as shown it is not.
Why is this?
> But the animation actually shows that after step 2, Q = [a1, a3, b1, b3]. In other words, a3 didn't join the back of the queue but jumped in front of b1. This is what leads to the buggy behavior that is shown.
This is my fault. The animation doesn't really point that out, but these are two separate queues: the forwards BFS and the backwards BFS each have their own queue. What the diagram shows is the order in which the nodes will be visited, according to the queues. So it's interleaved, in a way, since each step alternates the BFS that is executed.
However, suppose that Q actually be a "normal" queue. We'd then need to track, in the queue, which "way" the node should be visited (forwards or backwards). We'd be visiting more nodes at once per side but we'd still not visit levels at once before moving on to the other side, so it could still give the bad path sometimes. Also, since we'd only have one queue, we would be unable to efficiently detect a missing path: right now we check at each step if either of the queues is empty (and stop if that's the case). With a single queue, it would be slow to check if one side doesn't have any queued nodes, and without that check, for cases where no path exists, we'd waste time expanding a search on one side when it could never reach the destination anyway.
A connection that tickled my fancy...
In the "Finding Paths, Faster" section it specifies:
1. that we can only use the standard A* algo when we know enough about "the graph in question" to exploit that knowledge to pick a heuristic.
2. When we don't know anything specific to "the graph in question", we need to rely on BFS or by extension BiDi BFS (Bi-directional BFS) to find the shortest path in general.
Then way down the page in the "Finding the Right Path, Faster" section it specifies an optimisation for speeding up a correct BiDi BFS algo in a general graph is to order our searching by always check the side with the least queued branches.
The connection comes from realising that while we might not know anything specific to the graph in question, we know enough about graphs in general (of which "the graph" is one) that gives us enough knowledge to exploit the graph in question.
So a BiDi BFS where we repeatedly choose the side with the fewest branches IS essentially a BiDi A* algo that can be applied on a general graph.
Or put another way, Unidirectional A* search can't be used on a general graph, but Bidirectional A* search can.
Had a lot of fun making the animations for this one.
I was about to post this after seeing it on lobste.rs. Really underrated on hackernews for some reason