I'm using BGL for the johnson_all_pairs_shortest_path algorithm, and spending about 98% of my runtime in that algorithm. Breaking it down, the BFS_visit itself is consuming some 85% of my total runtime. Hence, any and every improvement I can get in my BGL performance will make my app much much snappier. Currently, my graph type is a adjacency_list <vecS, vecS, undirectedS, no_property, property <edge_weight_t, double> > and I'm wondering if that's the best choice. My graph has (E=2*V), and all nodes are of constant degree, with 4 edges incident on them. V is usually in the range of 150-500. Would one of the other types (such as listS) perhaps be faster, and still work? I know some BGL algorithms require certain graph storage types, so I'm hesitant to just start poking around and trying random things. That, and other than "listS", I don't know of any other types of graph, as I'm quite new to both the BGL and boost in general. Any thoughts on what might make things faster? Additionally, are there any compiler flags I should consider other than the 'vanilla' ones? (-O3). I'm using GCC 4.0.1 currently, if it matters. Thanks for the great library, and such a friendly list, Greg Link