Name of double sided search algorithms I modeled the function double_sided_breadth_first_search after the ideas in "improving Dijkstra" in Cormen et al, and the OCW course on algorithms. Note that I expand the smaller boundary, in an effort to improve efficiency. I have not seen this applied to bfs before. Does anyone know the name of this algorithm? Does it have a name? I saw the technique for doing a double sided Dijkstra algorithm, doing the iteration on the smaller vertex with smaller degree described online but can't find the page now. Does anyone know of a references for the Dijkstra style algorithm I just described?

More detailed description of algorithm I am trying to research:
  Do a two sided breadth first search starting at both vertices. At each iteration expand the boundary of the smaller boundary.

The pseudo code is as follows  

double_sided_breadth_first_search( ug, vertex0, vertex1 )  
  #ug undirected graph as an adjacency list, ie hash map from vertex to set of neighbor vertices  
  # vertex0, vertex1 - the two vertices that we wan't to connect  
  boundary0 = { vertex0 }  
  boundary1 = { vertex1 }  
  visited = hashmap from vertex =&gt; vertex0 or vertex1  
  common_vertex = null  
  distance = 0 
  while |boundary0| &gt; 0 and |boundary1| &gt; 0 and common_vertex is null {  
    distance = distance + 1  
    if |boundary0| &lt;= |boundary1| then  
       expand boundary0, mark vertices in new boundary with vertex0  
        set common_vertex if one is marked as vertex1  
    else  
       expand boundary1, mark vertices in new boundary with vertex1  
        set common_vertex if one is marked as vertex0  
  }  
  if common_vertex not null {  
    return distance  
  } else {  
    error  
  }  


Here is python code that implements the algorithm
What you have implemented is a variation of bidirectional Dijksktra's algorithm.

Bidirectional search is a graph search algorithm that finds a shortest path from an initial vertex to a goal vertex in a directed or undirected graph. It runs two simultaneous searches: one forward from the initial state, and one backward from the goal, stopping when the two meet. When each search is Dijkstra's algorithm, we end up with bidirectional Dijkstra's algorithm.

In which order the algorithm should expand the search in each direction and in which efficient condition the algorithm can stop the search are two obvious and critical factors for a bidirectional search. They are studied in quite a few papers.

It looks like there is not a special or specific name for the variation of bidirectional Dijkstra's algorithm that expands the search from the side whose front is nearer to its starting points. One reason to explain away the lack of a name is that it is not easy to argue that strategy should offer a nicer heuristic when compared to other strategies.

You may want to read the Wikipedia article on bidirectional search.