On Sat, 22 Sep 2012, Leo Hidd wrote:

I'm the OP of that topic. With a great help of Jeremiah WillCock (thank you Jeremiah, you are a great and very patient man :) ), I could finally obtain an working case with CSR graphs (a great amount of messages were sent in private, so they do not appear in the list). Here's an example. Note that I don't provide the the class obj_Mesh, since the only variables I use from it are used to compute the number of edges and the cost of each edge. You can replace these info by your own.

The one thing I would change about the example is not to use &d[0] and &p[0] but to use an iterator_property_map instead (see <URL:http://comments.gmane.org/gmane.comp.lib.boost.user/67769>); using raw pointers has caused problems for various users in the past.

Thank you so much Jeremiah and Leo! I still need to implement Jeremiah's suggestion but the initial results look very positive.

In case it is of interest to others, after I changed to a CSR graph instead of an adjacency_list, and used the "boost::dijkstra_shortest_paths

_no_color_map" instead of the "boost::dijkstra_shortest_paths", both my running time and space requirements significantly dropped.

For a graph with ~3,600,000 nodes and ~580,000,000 edges, after making these changes, my running time went down from about 1.5 hrs to 20 mins and my space requirements went from 95GB to 35 GB.

Thanks again!
- Jeremy