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.[1]

Implementation

The example below uses two simultaneous breadth-first searches. 

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;
}

References
  1. "Bidirectional search". Planning Algorithms. UIUC. Archived from the original on 21 February 2020. Retrieved 11 October 2020.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.