The stopping criteria, as I understand, for a bidirectional Dijkstra's search (with a single start and terminal state) is as follows
Start with a variable mu = infinity Start search from start (s) and terminal states (t) When the two intersect (either the node we are currently looking at from the forward search is in the reverse search or vice versa) at node w, then recalculate mu to be
mu = distance(s,w) + distance(w,t)
Then you check if the top two nodes (the next ones to be examined) have a combined distance >= mu, and if they do, terminate
if distance(s, top_forward_node) + distance(top_reverse_node, t) >= mu, stop
But if I try this on a simple triangle, it fails. Say I have a triangle (a,b,c) with ab = 10, bc = 6 and ac = 7. Start state = a and terminal state = b. Clearly, the shortest distance is ab = 10. But the forward pass starts at a and looks at both b (10) and c (7) and the reverse pass starts at b and looks at a (10) and c (6). Since c is the node with the lowest cost, the forward pass looks at c, but since it isn't in the reverse nodes already looked at, it stores it and moves to the reverse pass. The reverse pass looks at c and sees that it is in the nodes looked at by the forward pass, and updates the mu value from infinity to 7 + 6. The next nodes to be looked at are b and a, with path cost of 10 each, but then if I simply add the two (10 + 10), I get a value of 20 which is >= 7 + 6, so my algorithm incorrectly terminates with a path of a-c-b. Where am I going wrong?
forward pass explored nodes = [a(0)]
reverse pass explored nodes = [b(0)]
forward pass frontier nodes = [c(7), b(10)]
reverse pass frontier nodes = [c(6), a(10)]
explore c(7) from forward pass frontier nodes. Is it in reverse pass explored nodes? No. Move on
forward pass explored nodes = [a(0), c(7)]
forward pass frontier nodes = [b(10)]
explore c(6) from reverse pass frontier nodes. Is it in forward pass explored nodes? Yes. Recalculate mu
mu = distance(a,c) + distance(c,b) = 6 + 7 = 13
reverse pass explored nodes = [b(0), c(6)]
reverse pass frontier nodes = [a(10)]
check termination
top_node(forward pass frontier nodes) + top_node(reverse pass frontier nodes) >= mu
10 + 10 > 13?
yes. Return path a-c-b
Reference: Slide 10 on http://www.cs.princeton.edu/courses/archive/spr06/cos423/Handouts/EPP%20shortest%20path%20algorithms.pdf
This answer doesn't help me: Termination Criteria for Bidirectional Search
I figured out where I was going wrong. In the check to see if I've intersected with the opposite search, I should check both frontier and explored nodes, not just explored nodes. Doing so will give the correct result.