Threading of Dijkstra's algorithm

Topics: algorithm, graph
Jun 17, 2009 at 1:02 PM
Edited Jun 17, 2009 at 1:03 PM

Hi,

I have a large dataset that is regularly updated and I would like to make use of Azure to process this using Dijkstra's algorithm in a parallel / threaded manner.

I appreciate that there is the potential for a lot of locking conflicts using this approach so my question is;

Are there any good approaches to scaling Dijkstra's algorithm? I can't see a way to split the graph between threads, if I can't do that then I'll have to look at the costs of synchronizing access to the graph in Azure storage.

Thanks in advance

 

Ryan

Coordinator
Jun 18, 2009 at 12:13 AM

Dijkstra is basically a breadth first search with a priority queue. Look for 'Scalable Distributed Parallel Breadth First Search' in the literrature.

Jun 18, 2009 at 6:11 PM

Thanks, I can find general references to this algorithm on the web but none in the quickgraph docs. Did you mean that QG already has support for this or that I should look elsewhere as I cannot see it.

 

Regards

 

Ryan

Coordinator
Jun 19, 2009 at 5:08 AM

No support yet for this kind of computation. The only I know is http://www.osl.iu.edu/research/pbgl/