Re: [Boost-users] [Graph] On Dijkstra SSSP performance

Subject: Re: [Boost-users] [Graph] On Dijkstra SSSP performance
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2012-03-06 15:56:02

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