On Tue, 6 Mar 2012, Leo Hidd wrote:
Sorry Jeremiah, my bad, the #4 is with vecS instead of listS, my bad (bad copy-paste....), so the #3 plus optimizations.
Could you please also try compressed_sparse_row_graph (you can just build one from your adjacency list for testing purposes)? You might also want to try dijkstra_shortest_paths_no_color_map, but I'm not sure that will help your performance.
As for the vector vs array new, yes, I know, but since it has some overhead when accessing elements, it makes it slower (comparing #1 to #2 makes it very explicit)
Which compiler are you using? Do you have a small test program you can send, preferably with a synthetic data set (or a reference to one from the University of Florida sparse matrix collection or similar)? -- Jeremiah Willcock