[zdimension]

> 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.