On Fri, 22 May 2009, Lennart Berg wrote:
Thanks for the reply, I am not sure yet how to use adjancy list effectively to improve the speed... I am looking for some inspiration on google now.. If you could provide me with some short pseudo code or an example, that would be grat
(snip) One potential issue is that BGL performance in debug mode is not representative of what will happen in release mode. Also, it appears that you are completely rebuilding the graph in every round of your game. If that is true, you might want to use the compressed_sparse_row_graph and its sorted add_edge operation in all versions of the CSR graph; or pre-build a sequence of pairs and corresponding distances (possibly unsorted) using the constructors coming out in 1.40 and that are currently in the trunk. The CSR graph type tends to be faster for read-only access, and its sorted add_edge function is also fast. It is only for directed graphs, but you should be able to insert each distance twice (once for each direction) if your distances are all positive. Also, x86 performance of Dijkstra is ~25% better on the trunk than in 1.38 (and probably 1.39) so you might want to benchmark against that; again, release mode is important to get accurate performance information. -- Jeremiah Willcock