# 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 => vertex0 or vertex1
common_vertex = null
distance = 0
while |boundary0| > 0 and |boundary1| > 0 and common_vertex is null {
distance = distance + 1
if |boundary0| <= |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
}

• Do you mean the name of the algorithm that expands the smaller boundary first? Or the name for double sided Dijkstra algorithm, which is bidirectional Dijkstra's algorithm? – Apass.Jack Mar 16 at 0:42
• @apass.jack, I was asking for the names of both algorithms, both for improving DIjkstra, and for improving BFS. – Clark Sims Mar 16 at 0:50
• @D.W, I posted a link the the python code. To my eye Python reads like pseudo code. I always liked writing psuedo code that looks almost exactly like python, so I usually code it into python, just to check that my intuition makes sense. The basic idea is that one is doing a breadth first search starting at two points vertex0, and vertex1. One expands the smaller boundary at each iteration, because that increases the length the solution with less work than the larger boundary. Similar techniques have been done with Dijkstra. – Clark Sims Mar 16 at 0:50
• @dw, is that better? – Clark Sims Mar 16 at 1:33