Definition

Bidirectional search is a graph search algorithm which find smallest path form source to goal vertex. It runs two simultaneous search:

1. Forward search form source/initial vertex toward goal vertex
2. Backward search form goal/target vertex toward source vertex

Example

public int openLockBidirectional(String[] deadends, String target) {
        Set<String> blocks = new HashSet<>();
        Collections.addAll(blocks, deadends);
        String start = "0000";
        if (blocks.contains(start)) return -1;
        if (start.equals(target)) return 0;

				**//add start to begin set and end to end set**
        Set<String> beginSet = new HashSet<>() {{
            add(start);
        }};
        Set<String> endSet = new HashSet<>() {{
            add(target);
        }};

        int lvl = 0;
        while (!beginSet.isEmpty() && !endSet.isEmpty()) {
            lvl++;
            **//always pick smallest**
            if (beginSet.size() > endSet.size()) {
                Set<String> tmp = beginSet;
                beginSet = endSet;
                endSet = tmp;
            }
						**//tmp is next lvl**
            Set<String> tmp = new HashSet<>();
            for (String node : beginSet) {
                **//take adjacent and verify condition**
                for (String adj : getAdjacentNodes(node)) {
                    if (!blocks.contains(adj)) {
                        tmp.add(adj);
                        blocks.add(node);
                        if (endSet.contains(adj)) {
                            return lvl;
                        }
                    }
                }
            }
            beginSet = tmp;
        }
        return -1;
    }

Untitled

Time & Space complexity

O(b^(d/2))

where b - branching factor and d - distance to end node