I 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?