title: Stopping criteria for a bidirectional Dijkstra's (or uniform cost search) algorithm
body: <p>The stopping criteria, as I understand, for a bidirectional Dijkstra's search (with a single start and terminal state) is as follows</p>
  
  <p>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 </p>
  
  <pre><code>mu = distance(s,w) + distance(w,t)
  </code></pre>
  
  <p>Then you check if the top two nodes (the next ones to be examined) have a combined distance >= mu, and if they do, terminate</p>
  
  <pre><code>if distance(s, top_forward_node) + distance(top_reverse_node, t) &gt;= mu, stop
  </code></pre>
  
  <p>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?</p>
  
  <pre><code>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)]
  </code></pre>
  
  <p>explore c(7) from forward pass frontier nodes. Is it in reverse pass explored nodes? No. Move on</p>
  
  <pre><code>forward pass explored nodes = [a(0), c(7)]
  forward pass frontier nodes = [b(10)]
  </code></pre>
  
  <p>explore c(6) from reverse pass frontier nodes. Is it in forward pass explored nodes? Yes. Recalculate mu</p>
  
  <pre><code>mu = distance(a,c) + distance(c,b) = 6 + 7 = 13
  reverse pass explored nodes = [b(0), c(6)]
  reverse pass frontier nodes = [a(10)]
  </code></pre>
  
  <p>check termination</p>
  
  <pre><code>top_node(forward pass frontier nodes) + top_node(reverse pass frontier nodes) &gt;= mu
  10 + 10 &gt; 13?
  </code></pre>
  
  <p>yes. Return path a-c-b</p>
  
  <p>Reference: Slide 10 on <a href="http://www.cs.princeton.edu/courses/archive/spr06/cos423/Handouts/EPP%20shortest%20path%20algorithms.pdf" rel="nofollow noreferrer">http://www.cs.princeton.edu/courses/archive/spr06/cos423/Handouts/EPP%20shortest%20path%20algorithms.pdf</a></p>
  
  <p>This answer doesn't help me: <a href="https://stackoverflow.com/questions/4253413/termination-criteria-for-bidirectional-search">Termination Criteria for Bidirectional Search</a></p>