Here are some ideas: Do you need all of the properties in the explorer threads? maybe you can construct a somewhat cheap copy of the graph of just vertices, edges and weights?
Unfortunately no, my graph has 5 million of vertices and 10 million of edges, and the properties RAM cost is very lower confronted to the graph structure. The graph structure takes approximately the same RAM quantity of the graph + properties. Moreover I've tried to make a graph copy, but it takes about 30 seconds on my machine (Pentium D 2.8GHz, 3Gb RAM, WinXP); it's too much confronted to the Dijkstra's time (about 6-7 seconds).
When each explorer thread runs an instance of Dijkstra you might consider a parallel version of Dijkstra [1,2] working on disjoint graph regions? That might allow you to cut the graph into pieces and assigning a 'local' version of the graph to each explorer thread and joining them later on?
These arguments are relatively new to me... do you think that's the way? I've take a look to PBGL and MTGL: https://software.sandia.gov/trac/mtgl/ http://www.osl.iu.edu/research/pbgl/ Maybe I can use them to resolve my problem? Thanks, Cosimo Calabrese.