title: Termination Criteria for Bidirectional Search
body: <p>According to most of the reading I have done, a bidirectional search algorithm is said to terminate when the "forward" and "backward" frontiers first intersect. However, in Section 3.4.6 of <em>Artificial Intelligence: A Modern Approach</em>, Russel and Norvig state:</p>
  
  <blockquote>
    <p>Bidirectional search is implemented by replacing the goal test with a check to see
    whether the frontiers of the two searches intersect; if they do, a solution has been found.
    It is important to realize that the first solution found may not be optimal, <strong>even if the
    two searches are both breadth-first; some additional search is required to make sure there
    isn't a shortcut across the gap.</strong></p>
  </blockquote>
  
  <p>I have considered this statement for quite some time, but am unable to find an example of this behavior. Can anyone provide an example graph where the first intersection between the forward and backward frontiers of a bidirectional BFS or A* search is not the shortest path?</p>
  
  <p><strong>Edit:</strong> Clearly BFS will not find the shortest path in a weighted graph. It sounds like this excerpt is referring to bidirectional BFS on a undirected graph. Alternatively, I would be interested in seeing a counterexample using bidirectional A* on a weighted graph. </p>