2
$\begingroup$

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  
  }  

Here is python code that implements the algorithm

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Apass.Jack Mar 16 at 0:42
  • $\begingroup$ @apass.jack, I was asking for the names of both algorithms, both for improving DIjkstra, and for improving BFS. $\endgroup$ – Clark Sims Mar 16 at 0:50
  • $\begingroup$ @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. $\endgroup$ – Clark Sims Mar 16 at 0:50
  • $\begingroup$ @dw, is that better? $\endgroup$ – Clark Sims Mar 16 at 1:33
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.