I saw this via Lobsters yesterday and enjoyed reading it. The animations helped me understand bidiBFS.<p>But I'm confused by the example showing the buggy version of the algorithm fail. This is in the section "Finding the Wrong Path".<p>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].<p>In the next step we explore T, the first node in the queue. We add its neighbors , a3 and b2, to the queue.<p>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.<p>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.<p>So as I understand the example, this would have worked fine if Q were actually a queue. But as shown it is not.<p>Why is this?
A connection that tickled my fancy...<p>In the "Finding Paths, Faster" section it specifies:<p>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.<p>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.<p>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.<p>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.<p>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.<p>Or put another way, Unidirectional A* search can't be used on a general graph, but Bidirectional A* search can.