Bidirectional search

In computer science, bidirectional search is a method used for finding the shortest path between two items in a graph. It runs two simultaneous searches starting from the two items.

Implementation

The example below uses two simultaneous breadth-first searches. <syntaxhighlight lang="java"> void bidirectionalSearch(Item a, Item b) {

   Queue qA = new Queue();
   Queue qB = new Queue();
   qA.enqueue(a);
   qB.enqueue(b);
   while (!qA.isEmpty() && !qB.isEmpty()) {
       if (!qA.isEmpty()) {
           Item v = qA.dequeue();
           if (aItem.found) return true;
           for (Item neighbor : v.neighbors()) {
               if (!neighbor.found) {
                   neighbor.found = true;
                   qA.enqueue(neighbor);
               }
           }
       }
       if (!qB.isEmpty()) {
           Item v = qB.dequeue();
           if (v.found) return true;
           for (Item neighbor : v.neighbors()) {
               if (!neighbor.found) {
                   neighbor.found = true;
                   qB.enqueue(neighbor);
               }
           }
       }
   }
   return false;

} </syntaxhighlight>

Related pages

• Breadth-first search